solved 'Insertion Sort List' on LeetCode (1 compile error then AC, not bad :-) http://oj.leetcode.com/problems/insertion-sort-list/

insertion_sort_list.cpp

/**
 * 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 head;
        this->head = head;
        while (head->next != NULL)
        {
            bool proceedOrNot = 1; // ugly, but worked
            ListNode *nextAfterInsert = insertion(head->next, proceedOrNot);
            if (proceedOrNot)
                head = head->next;
            else
                head->next = nextAfterInsert;
        }
        return this->head;
    }
private:
    ListNode *head;

    ListNode *insertion(ListNode *curr, bool &proceedOrNot)
    {
        ListNode *next = curr->next;
        if (head->val > curr->val)
        {
            curr->next = head;
            head = curr;
            proceedOrNot = 0;
        }
        else
        {
            ListNode *iter = head;
            while (iter->next != curr)
            {
                if (iter->next->val >= curr->val)
                {
                    curr->next = iter->next;
                    iter->next = curr;
                    proceedOrNot = 0;
                    break;
                }
                else
                    iter = iter->next;
            }
        }
        return next;
    }
};