How do you sort a linked list? Write a C program to sort a linked list.
This is a very popular interview question, which most people go wrong. The ideal solution to this problem is to keep the linked list sorted as you build it. Another question on this website teaches you how to insert elements into a linked list in the sorted order. This really saves a lot of time which would have been required to sort it.
However, you need to Get That Job....
Method1 (Usual method)
The general idea is to decide upon a sorting algorithm (say bubble sort). Then, one needs to come up with different scenarios to swap two nodes in the linked list when they are not in the required order. The different scenarios would be something like
1. When the nodes being compared are not adjacent and one of them is the first node.
2. When the nodes being compared are not adjacent and none of them is the first node
3. When the nodes being compared are adjacent and one of them is the first node.
4. When the nodes being compared are adjacent and none of them is the first node.
One example bubble sort for a linked list goes like this (working C code!)....
#include<stdio.h>
#include<ctype.h>
typedef struct node
{
int value;
struct node *next;
struct node *prev;
}mynode ;
void add_node(struct node **head, int *count, int value);
void print_list(char *listName, struct node *head);
mynode *bubbleSort(mynode *head, int count);
int main()
{
mynode *head;
int count = 0;
head = (struct node *)NULL;
add_node(&head, &count, 100);
add_node(&head, &count, 3);
add_node(&head, &count, 90);
add_node(&head, &count, 7);
add_node(&head, &count, 9);
print_list("myList(BEFORE)", head);
head = bubbleSort(head, count);
print_list("myList(AFTER) ", head);
getch();
return(0);
}
mynode *bubbleSort(mynode *head, int count)
{
int i, j;
mynode *p0, *p1, *p2, *p3;
for(i = 1; i < count; i++)
{
p0 = (struct node *)NULL;
p1 = head;
p2 = head->next;
p3 = p2->next;
for(j = 1; j <= (count - i); j++)
{
if(p1->value > p2->value)
{
// Adjust the pointers...
p1->next = p3;
p2->next = p1;
if(p0)p0->next=p2;
// Set the head pointer if it was changed...
if(head == p1)head=p2;
// Progress the pointers
p0 = p2;
p2 = p1->next;
p3 = p3->next!=(struct node *)NULL?p3->next: (struct node *)NULL;
}
else
{
// Nothing to swap, just progress the pointers...
p0 = p1;
p1 = p2;
p2 = p3;
p3 = p3->next!=(struct node *)NULL?p3->next: (struct node *)NULL;
}
}
}
return(head);
}
void add_node(struct node **head, int *count, int value)
{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;
if(*head == NULL)
{
*head=temp;
temp->value=value;
}
else
{
for(cur=*head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
}
*count = *count + 1;
}
void print_list(char *listName, struct node *head)
{
mynode *temp;
printf("\n[%s] -> ", listName);
for(temp=head;temp!=NULL;temp=temp->next)
{
printf("[%d]->",temp->value);
}
printf("NULL\n");
}
As you can see, the code becomes quite messy because of the pointer logic. Thats why I have not elaborated too much on the code, nor on variations such as sorting a doubly linked list. You have to do it yourself once to understand it.
Method2 (Divide and Conquer using Merge Sort)
Here is some cool working C code...
#include<stdio.h>
#include<ctype.h>
typedef struct node
{
int value;
struct node *next;
struct node *prev;
}mynode ;
void add_node(struct node **head, int value);
void print_list(char *listName, struct node *head);
void mergeSort(struct node** headRef);
struct node *merge2SortedLLs(struct node *head1, struct node *head2);
void splitLLInto2(struct node* source, struct node** frontRef, struct node** backRef);
// The main function..
int main()
{
mynode *head;
head = (struct node *)NULL;
add_node(&head, 1);
add_node(&head, 10);
add_node(&head, 5);
add_node(&head, 70);
add_node(&head, 9);
add_node(&head, -99);
add_node(&head, 0);
print_list("myList", head);
mergeSort(&head);
print_list("myList", head);
getch();
return(0);
}
// This is a recursive mergeSort function...
void mergeSort(struct node** headRef)
{
struct node* head = *headRef;
struct node* a;
struct node* b;
// Base case -- length 0 or 1
if ((head == NULL) || (head->next == NULL))
{
return;
}
// Split head into 'a' and 'b' sublists
splitLLInto2(head, &a, &b);
// Recursively sort the sublists
mergeSort(&a);
mergeSort(&b);
// Merge the two sorted lists together
*headRef = merge2SortedLLs(a, b);
}
// This is an iterative function that joins two already sorted
// Linked lists...
struct node *merge2SortedLLs(struct node *head1, struct node *head2)
{
struct node *a, *b, *c, *newHead, *temp;
a = head1;
b = head2;
c = (struct node *)NULL;
newHead = (struct node*)NULL;
if(a==NULL)return(b);
else if(b==NULL)return(a);
while(a!=NULL && b!=NULL)
{
if(a->value < b->value)
{
//printf("\na->value < b->value\n");
if(c==NULL)
{
c = a;
}
else
{
c->next = a;
c = c->next;
}
a = a->next;
}
else if(a->value > b->value)
{
//printf("\na->value > b->value\n");
if(c==NULL)
{
c = b;
}
else
{
c->next = b;
c = c->next;
}
b = b->next;
}
else
{
// Both are equal.
// Arbitraritly chose to add one of them and make
// sure you skip both!
if(c == NULL)
{
c = a;
}
else
{
c->next = a;
c = c->next;
}
a = a->next;
b = b->next;
}
// Make sure the new head is set...
if(newHead == NULL)
newHead = c;
}
if(a==NULL && b==NULL)
return(newHead);
if(a==NULL)
c->next = b;
else if(b==NULL)
c->next = a;
return(newHead);
}
// Uses the fast/slow pointer strategy
//
// This efficient code splits a linked list into two using
// the same technique as the one used to find the
// middle of a linked list!
void splitLLInto2(struct node* source, struct node** frontRef, struct node** backRef)
{
struct node* fast;
struct node* slow;
if (source==NULL || source->next==NULL)
{
// length < 2 cases
*frontRef = source;
*backRef = NULL;
}
else
{
slow = source;
fast = source->next;
// Advance 'fast' two nodes, and advance 'slow' one node
while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}
// 'slow' is before the midpoint in the list, so split it in two
// at that point.
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
}
void add_node(struct node **head, int value)
{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;
if(*head == NULL)
{
*head=temp;
temp->value=value;
}
else
{
for(cur=*head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
}
}
void print_list(char *listName, struct node *head)
{
mynode *temp;
printf("\n[%s] -> ", listName);
for(temp=head;temp!=NULL;temp=temp->next)
{
printf("[%d]->",temp->value);
}
printf("NULL\n");
}
The code to merge two already sorted sub-linked lists into a sorted linked list could be either iterative or recursive. You already saw the iterative version above. Here is a recursive version of the same...
Recursive solution to merge two already sorted linked lists into a single linked list
struct node* sortedMergeRecursive(struct node* a, struct node* b)
{
struct node* result = NULL;
if (a==NULL) return(b);
else if (b==NULL) return(a);
// Pick either a or b, and recur
if (a->data <= b->data)
{
result = a;
result->next = sortedMergeRecursive(a->next, b);
}
else
{
result = b;
result->next = sortedMergeRecursive(a, b->next);
}
return(result);
}
Also, see how the splitLLInto2() function uses the same technique used to find the middle of a linked list to split a linked list into two without having to keep a count of the number of nodes in the linkes list!
Here is another solution (not that great, though) to split a linked list into two. It used the count of the number of nodes to decide where to split
void splitLLInto2(struct node* source,struct node** frontRef, struct node** backRef)
{
int len = Length(source); //Get the length of the original LL..
int i;
struct node* current = source;
if (len < 2)
{
*frontRef = source;
*backRef = NULL;
}
else
{
int hopCount = (len-1)/2;
for (i = 0; i<hopCount; i++)
{
current = current->next;
}
// Now cut at current
*frontRef = source;
*backRef = current->next;
current->next = NULL;
}
}
Using recursive stack space proportional to the length of a list is not recommended. However, the recursion in this case is ok ? it uses stack space which is proportional to the log of the length of the list. For a 1000 node list, the recursion will only go about 10 deep. For a 2000 node list, it will go 11 deep. If you think about it, you can see that doubling the size of the list only increases the depth by 1.
Subscribe to:
Post Comments (Atom)
21 comments:
hey good job ... but i feel i have a simpler code... if u come across any bug do let me know
void sort()
{
struct node *t1,*t2,*t3;
int flag;
do
{
flag=0;
t1=start;
t2=t1->next;
t3=t2->next;
if(t1->data > t2->data)
{
start=t1->next;
t1->next=t3;
t2->next=t1;
flag=1;
t1=start;
t2=t1->next;
t3=t2->next;
}
while(t3!=NULL)
{
if(t2->data > t3->data)
{
flag=1;
t1->next=t3; t2->next=t3->next; t3->next=t2;
}
t1=t1->next;
t2=t1->next; t3=t2->next;
}
}
while(flag);
}
Good info :)
Just thot merge2SortedLLs can be optimized like this:
struct node *merge2SortedLLs(struct node *head1, struct node *head2)
{
NODE *a, *b, *c, *newHead, *temp;
NODE *old_a, *old_b;
a = head1;
b = head2;
c = (struct node *)NULL;
newHead = (struct node*)NULL;
if(a==NULL)return(b);
else if(b==NULL)return(a);
if(a->value < b->value)
{
c = newHead = a;
a = a->next;
}
else
{
c = newHead = b;
b = b->next;
}
while(a!=NULL && b!=NULL)
{
old_a = a;
old_b = b;
if (a->value < b->value)
{
c->next = a;
a = old_a->next;
}
else
{
c->next = b;
b = old_b->next;
}
c = c->next;
}
if(a==NULL)
c->next = b;
else if(b==NULL)
c->next = a;
return(newHead);
}
solution by alpana kabra is superb...
is it not simple to just swap the data. What is the advantage of swapping the pointers...seems very expensive operation
Surya-
I tried using the bubble sort logic to sort the linked list. below is the code
struct node
{
int info;
struct node *link;
};
typedef struct node *NODE;
NODE sort(NODE first)
{
NODE next = NULL, cur = NULL;
int count=0, i, j;
int tmp;
cur = first;
while(cur)
{
cur = cur->link;
count++;
}
cur = first;
next = cur->link;
for(j=1;jinfo >= next->info)
{
tmp = cur->info;
cur->info = next->info;
next->info = tmp;
}
cur = cur->link;
next = cur->link;
}
cur = first;
next = cur->link;
}
return first;
}
there is a mistake in ur code... in the for loop of variable j in fucnction bubblesort()... it should be "j<count-i" in place of "j<=count-i"..otherwise it is giving segmentation fault.. :)
Hi How about this,
1. Take a sortedHead node
2. Save next of the linked list
3. Insert current node into to sortedHead in sorted fashion
Here is the Pseudocode for sorting linked list
LL sortedHead = NULL;
LL iter = list;
while(iter)
{
next = iter->next;
InsSortedLL(sortedHead, iter);
iter = next;
}
return sortedHead;
//Function to insert node according to the sorted order
InsSortedLL(sortedHead, node)
{
//Insert in sorted order
}
I have read so many articles or reviews concerning the blogger lovers except this article is
genuinely a nice article, keep it up.
Also visit my web-site; sian
Eveгyone loves it whenever peoplе
come together and ѕhare іԁеaѕ.
Great site, stick ωith it!
Alѕo ѵisit my pagе: same chat room
Тhis design іs spеctacular! You obviously knoω how to keeр a reаdеr entertainеd.
Between уouг ωit anԁ yоur vidеoѕ,
ӏ was аlmοst moνed to ѕtart my oωn blοg (ωell, almost.
..HaHa!) Grеat job. I rеally enjoyed ωhаt you had to say, anԁ more thаn that, how уou ρresentеd it.
Τοo cοol!
My homеpage; Russian Website
If you desire to get a greаt deal from this post then уou haѵe to apply
such methοds to yοur ωon weblog.
mу page; social media sites
I love it when folκs get together anԁ share ideas.
Great blog, stick with it!
Look into my page - haemorrhoiden
Thanκs for shаring your thοughts about snеaκ prеvieω.
Regards
my blog: chat for free
I fοг all tіme еmailed thiѕ website poѕt page
to all my associateѕ, for the rеaѕοn that if like tο
read it then my contactѕ will too.
Also viѕit mу blog post: chatroulette
Wow, this pіеce of wгiting іѕ fastidious,
mу sistеr is analyzing such things, therefore I am going to conveу
her.
My ωeb pаgе: chatroulette
hi!,I love your wгitіng ѕo so muсh!
share we communiсatе more appгoximatelу
уouг pοst on AOL? І require
an expеrt on this house tо гesοlvе my problem.
Maybe that's you! Looking forward to look you.
Here is my site; curing hemorrhoids
It's going to be end of mine day, except before finish I am reading this fantastic post to increase my experience.
My weblog - Haarausfall
Verу quickly thіs website ωill be famous among
аll blogging and site-building people, duе to it's nice articles
Also visit my web blog - http://abnehmenweg.wordpress.com/2013/03/06/bauch-weg-trainieren-frau-die-abnehm-lsung-download
I visitеd νarious ωeb ρages but
the audio quаlity for audіo songs cuггent at this web
site is actuallу eхcellent.
Also viѕit my webpаge Taufgeschenke
Hmm is anyone elsе еncоuntering problems ωіth thе pіctures οn thiѕ blog loading?
I'm trying to figure out if its a problem on my end or if it's the
blog. Any suggeѕtіons ωould be gгеatly
apρreсіatеd.
Check out my hοmeраge ...
avoid premature ejaculation
kd shoes
fear of god essentials hoodie
supreme
off white clothing
nike sb
golden goose
goyard handbag
jordan shoes
goyard outlet
nike off white
Post a Comment