Problem description:
Sort a linked list using insertion sort.

Analysis:
The insertion sort of linked list can be done in O(1) space. In this solution, I create a node, result, to contain the result. The result would be look like the following graph.

-init state-
Original: 1 3 2 4 5
result->null

-first round-
Original: 3 2 4 5
result->1->NULL

I use the next pointer to temporally save the position in the original list. The iter already move to the position in the result list that contains value higher than head->val. Then adjust the pointer in these item to direct head node to result list and move to next item in original list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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) {
        ListNode result(INT_MIN);
        
        while(head){
            ListNode* iter = &result;
            while(iter->next && (iter->next->val < head->val)){ 
                //when result list gets long, use this to find proper position in result list.
                iter = iter->next;
            }
            ListNode* next = head->next;
            head->next = iter->next;
            iter->next = head;
            head = next;
        }
        return result.next;
    }
};

Reference:
https://goo.gl/dzL3m1