leetcode/Insertion_Sort_List.cpp at master · panzg123/leetcode · GitHub

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
28
29
30
31
32
33
34
/**
 * 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 dummy(INT_MIN);
        //dummy.next = head;
        for (ListNode *cur = head; cur != nullptr;)
            {
                auto pos = findInsertPos(&dummy, cur->val);
                ListNode *tmp = cur->next;
                cur->next = pos->next;
                pos->next = cur;
                cur = tmp;
            }
        return dummy.next;
    }
    ListNode* findInsertPos(ListNode *head, int x)
    {
        ListNode *pre = nullptr;
        for (ListNode *cur = head; cur != nullptr && cur->val <= x;
                pre = cur, cur = cur->next)
            ;
        return pre;
    }
};