[LeetCode] Insertion Sort List

Problem Statement (link):
Sort a linked list using insertion sort.
Analysis:
We traverse the linked list, once we find a node has a smaller value than that of its previous node, we start another traversal from the very beginning of the linked list to find the right position for that node to insert in.

Note:
- Once we found an unordered node and re-insert it to the right position, we should not advance the prev pointer. For instance: we have 2->4->1->3, the prev pointer points to node 4, and the tmp pointer points to node 1, i.e., we need to re-insert node 1 to its right position. After re-insertion, the list becomes: 1->2->4->3, the prev pointer still points to node 4, if we advance prev to node 3, we would miss re-insertion of node 3. The bool flag is for this purpose.

Extra link:
A very good review of sorting algorithms is summarized here by Yu.

Code: 

/**
 * 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;
        bool inserted=false;
        ListNode *prev=new ListNode(INT_MIN);
        prev->next=head;
        ListNode *begin=prev;

        while(prev->next->next!=NULL) {
            ListNode *cur=prev->next;
            ListNode* tmp=cur->next;
            if (cur->val>tmp->val) {
                locate(begin, cur, tmp);
                inserted=true;
            }
            else if (prev->next->next!=NULL && inserted==false) {
                prev=prev->next;
                inserted=false;
            }
            else
                prev=prev->next;
        }
        return begin->next;
    }

    // locate and insert target node
    void locate(ListNode* begin, ListNode* prev, ListNode* target) { 
        while(begin->next->val<target->val)
            begin=begin->next;

        // insert
        ListNode* tmp=target->next;
        target->next=begin->next;
        prev->next=tmp;
        begin->next=target;
    }
};