List->Dynamic List->Sorting

But for now, let's see the Insertion sort for the linked list. The principle goes like this - check for every element( in the unsorted list) whether there exists an element in the sorted list which is just greater than it, then just INSERT this current element exactly before it, in the sorted list. If you find no element in the sorted list to satisfy the condition, please insert the current element at the end of the sorted list. Check out the algo...

Algorithm:-
Step-1: Compare the current element in the UNSORTED list with each element in the SORTED list. If you find an element in the SORTED list to have just higher value than our current element then go to step-2 or else go to step-3
Step-2: Make the element with that just higher value as your TARGET position. Insert the current element at a position just before the TARGET. Consider the next element, if any and go to step-1 or else quit
Step-3: If you find the current element under consideration in the sorted list as the LAST element then just insert your current element from the unsorted list at the end of the Sorted list or else just move to the next element in the sorted list. Consider the next element, if any and go to step-1 or else quit 

C implementation:-
struct NODE
{
int nodevalue;
struct NODE *next;
}
struct NODE *uslist, *slist;
struct NODE *cur_us, *cur_s; /*pointers to surf the lists*/
main()
{
..
/*uslist and slist have been initialised here*/
/*uslist holds the list to be sorted*/
/*slist is initially empty as nothing is sorted*/
..
..
LLsort();
}

LLsort ( )
{
int delval; 
struct NODE *temp;

slist->nodevalue = 0; /*sorted list will have 0 as its first element initially*/
slist->next = NULL;
cur_us = uslist;

while( cur_us != NULL)
{
  cur_s = slist;  
 while(cur_s != NULL)
  {
   if(cur_us->nodevalue < cur_s->nodevalue)    /*step-1 of the algo.*/
   {
    target = cur_s;    /*step-2: make cur_s as your TARGET*/
    delval = delnode(cur_us); /*deletion has to be done to the UNSORTED list*/
    addnode(delval, target);  /*remember addition has to be done to the SORTED list*/
   }
   else
     if(cur_s->next == NULL)   /*step-3:if cur_s is the last element in the sorted list*/
       {
        delval = delnode(cur_us);
        temp_us = (struct NODE *)malloc(sizeof(NODE));   
        temp_us ->nodevalue = delval;
        cur_s->next = temp_us;   /*step-3:append the unsorted element to the sorted list*/
        temp_us->next = NULL;
       }
   cur_s = cur_s->next;  
  }
cur_us = cur_us->next;
}
}

Note:-Write addnode() for this on your own, as I must say its a little different than what I have covered in the add & del section. Well, deletenode() can be referred from there but remember always you'll have to adjust the list pointer, 'uslist'. Remember, while writing the addnode(), you will have to consider the case when you add an element to the beginning of the SORTED list (not always) and the list pointer, 'slist', has to be adjusted. Alright! 

Related Operations:
Concept
Addition and Deletion of a node
Traversing of list
Searching for a particular Key
Sorting of list