leetcode-solution/code/148.sort-list.cpp at master · Testzero-wz/leetcode-solution · 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
 * @lc app=leetcode id=148 lang=cpp
 *
 * [148] Sort List
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode *sortList(ListNode *head)
    {
        return mergeSort(head);
    }

    ListNode *find_mid(ListNode *head)
    {
        // slow & fast pointer
        ListNode * slow = head;
        ListNode * fast = head;
        while (fast->next != nullptr && fast->next->next != nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
    ListNode *mergeSort(ListNode *node)
    {
        if (node == nullptr || node->next == nullptr)
            return node;
        ListNode *mid = find_mid(node);
        ListNode *left = node;
        ListNode *right = mid->next;
        mid->next = nullptr;
        return merge(mergeSort(left), mergeSort(right));
    }
    ListNode *merge(ListNode *list_a, ListNode *list_b)
    {
        ListNode *merged = new ListNode(0);
        ListNode *ptr = merged;
        while (list_a != nullptr && list_b != nullptr)
        {
            if (list_a->val < list_b->val)
            {
                ptr->next = list_a;
                list_a = list_a->next;
            }
            else
            {
                ptr->next = list_b;
                list_b = list_b->next;
            }
            ptr = ptr->next;
        }
        ptr->next = list_a != nullptr ? list_a : list_b;
        return merged->next;
    }
};
// @lc code=end