[Leetcode] Insertion Sort List

Sort a linked list using insertion sort.
Analysis:
Using the insertion sort algorithm, for each node x, iterate from the beginning of the list and look for a node which is greater than current one. Split and insert node x before the node; since the head may be changed, use a dummy head to handle the head node changes
The idea is simple but the implementation may be a little tricky, need to be careful. 

/**
 * 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* dummyHead = new ListNode(0);
  dummyHead->next = head;
  ListNode* curr = head;
  ListNode* currPrev = dummyHead;
  while (curr != NULL)
  {
   //don't use ListNode* p as head was changed
   ListNode* p = dummyHead->next;
   ListNode* prev = dummyHead;
   while (curr != p && p->val < curr->val)
   {
    prev = p;
    p = p->next;
   }

   ListNode* next = curr->next;
   if (p != curr)
   {
    prev->next = curr;
    curr->next = p;
    //note: don't forget to set the p next
    currPrev->next = next;
   }
   else
   {
    currPrev = curr;
   }

   curr = next;
  }

  ListNode* newHead = dummyHead->next;
  delete dummyHead;

  return newHead;
 }
};