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. This really saves a lot of time which would have been required to sort it.

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

for(i = 1; i < n; i++)
{
p1 = head;
p2 = head->next;
p3 = p2->next;
for(j = 1; j <= (n - i); j++)
{
if(p2->value < p3->value)
{
p2->next = p3->next;
p3->next = p2;
p1->next = p3;
p1 = p3;
p3 = p2->next;
}
else
{
p1 = p2;
p2 = p3;
p3 = p3->next;
}
}
}
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 soring a doubly linked list. You have to do it yourself once to understand it.

Method1 (Divide and Conquer using merge sort)
The pseudocode for this method is
typedef struct node
{
int value;
struct node *next;
}mynode;
mynode *head, *tail;
int size;
mynode *mergesort(mynode *list, int size);
void display(mynode *list);
mynode *mergesort(mynode *list, int size)
{
int size1, size2;
mynode *tempnode1, *tempnode2, *tempnode3;
if(size<=2)
{
if(size==1)
{
// Nothing to sort!
return(list);
}
else
{
if(list->value < list->next->value
{
// These 2 nodes are already in right order, no need to sor
t
return(list);
}
else
{
// Need to swap these 2 nodes
/* Here we have 2 nodes
*
* node 1 -> node2 -> NULL
*
* This should be converted to
*
* node2 -> node1 -> NULL
*
*/
tempnode1 = list;
tempnode2 = list->next;
tempnode2->next = tempnode1;
tempnode1->next = NULL;
return(tempnode2);
}
}
}
else
{
// The size of the linked list is more than 2.
// Need to split this linked list, sort the
// left and right sub-linked lists and merge.
// Split.
// tempnode1 will have the first half of the linked list of size
"size1".
// tempnode2 will have the second half of the linked list of size
"size2".
<CODE TO SPLIT THE LINKED LIST INTO TWO>
// Sort the two halves recursively
tempnode1 = mergesort(tempnode1, size1);
tempnode2 = mergesort(tempnode2, size2);
// Now merge the sorted lists back, let tempnode3 point to that n
ew list.
<CODE TO MERGE THE 2 LINKED LISTS BACK INTO A SINGLE SORTED LINKE
D LIST>
return(tempnode3);
}
}
The code to merge the two already sorted sub-linked lists into a sorted linked list could be
something like this..
mynode * merge(mynode *a, mynode *b)
{
mynode *i, *j, *k, *c;
i = a;
j = b;
c = getNewNode();
k = getNewNode();
while(i!=NULL && j!=NULL)
{
if(i->value < j->value)
{
k->next=i;
i=i->next;
}
else
{
k->next=j;
j=j->next;
}
}
if(i!=NULL)
k->next=i;
else
k->next=j;
return(c->next);
}