Sort a linked list using insertion sort.

/**
 * 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 *start = new ListNode();
         ListNode *cur = head;

         while(cur)
         {
             ListNode *pre = start;
             while(pre->next && cur->val > pre->next->val)
             {
                 pre = pre->next;
             }
             ListNode *next = cur->next;
             cur->next = pre->next;
             pre->next = cur;
             cur = next;
         }
         return start->next;
    }
};