Sorting a linked list

How do we sort a linked list? Try this method - this is simple insertion sort method. Easily implementable in LL.

1) Create a new list called sorted list

2) Take one node from list, delete it. And add it to the sorted list

3) Take the next node - nodenew, traverse through sorted list till you find a node with key value greater than nodenew, and insert the nodenew before this node. Of course you have to delete nodenew from original list.

4) Continue this process until the original list is empty.

The complexity - O(n²)

 struct node

{

  int n;

   struct node *next;

};

typedef struct node *NODEPTR: 

NODEPTR sortList(NODEPTR head)  
 {  
    NODEPTR newList = NULL;  
    while(head!=NULL)  
    {  
     NODEPTR temp = head;  
     head = head->next;  
     temp->next = NULL;  
     newList = insertSorted(newList,temp);  
    }  
    printList(newList);  
    return newList;  
 }  
 NODEPTR insertSorted(NODEPTR head,NODEPTR newnode)  
 {  
    NODEPTR temp, prevNode=head;  
    if(head==NULL)  
     return newnode;  
    temp = head;  
    while(temp!=NULL && temp->n <newnode->n)  
    {  
       prevNode = temp;  
       temp = temp->next;  
    }  
 if(temp==head){  
    newnode->next = head;  
    head = newnode;  
 }else{  
    prevNode->next = newnode;  
    newnode->next = temp;  
 }  
    return head;  
 }  

sortList function removes head - first node, of original list and inserts into the new list and continues till original list is empty.

insertSorted function keeps traversing the list until it finds  a node whose value is greater than node to be inserted. It keeps saving previous node. Once the greater value node - temp,   is found, newnode is inserted between previous node and temp.

Two special cases to be considered are

1. When the list is empty. The function adds newnode as head
2. When the newnode has a value less than head node. Then function adds the node before head and makes newnode as head node.