Leetcode -- Insertion Sort List

 /**  
  * 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 * dummy = new ListNode(INT_MIN);  
     dummy->next = new ListNode(INT_MAX);  
     while(head != NULL) {  
       ListNode * p = dummy;  
       while(!(head->val >= p->val && head->val <= p->next->val)) {  
         p = p->next;  
       }  
       ListNode * temp = p->next;  
       p->next = head;  
       head = head->next;  
       p->next->next = temp;  
     }  
     ListNode * q = dummy;  
     while(q->next->next != NULL) {  
       q = q->next;  
     }  
     delete q->next;  
     q->next = NULL;  
     return dummy->next;  
   }  
 };  

Recursion

/**
 * 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 || head->next == NULL) {
            return head;
        }      
        ListNode * sorted = insertionSortList(head->next);
        ListNode * dummy = new ListNode(-1);
        dummy->next = sorted;
     
        ListNode * p = dummy;
        while(p->next != NULL) {
            if(head->val <= p->next->val) {
                break;
            }
            p = p->next;
        }
        
        ListNode * temp = p->next;
        p->next = head;
        head->next = temp;  
     
        return dummy->next;        
    }
};