[LeetCode] Insertion Sort List

Link : Insertion Sort List

Sort a linked list using insertion sort.

Analysis:
Quite straight-forward, create a new linked list header,
a) get a list node in original list,
b) find the place to insert it
c) and insert it

Code says!

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   ListNode *insertionSortList(ListNode *head) {  
     if(head==NULL)  
       return NULL;  
     ListNode fake(0);  
     ListNode* tmp;  
     ListNode* cursor=head;  
     while(cursor!=NULL)  
     {  
       ListNode* p = &fake;  
       while( p->next && cursor->val > p->next->val ) // find place to insert  
         p=p->next;  
       tmp = cursor; // keep the address  
       cursor=cursor->next; // cursor moves to the next  
       tmp->next = p->next;   
       p->next=tmp;  
     }  
     return fake.next;  
   }  
 };