leetcode/Problems/0148.cpp at master · DimitrijeDobrota/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
35
36
37
class Solution {
  public:
    ListNode *sortList(ListNode *head) {
        if (!head || !head->next) return head;
        ListNode *mid = getMid(head), *left = sortList(head), *right = sortList(mid);
        return merge(left, right);
    }

    ListNode *merge(ListNode *list1, ListNode *list2) {
        ListNode head, *t = &head;

        while (list1 && list2) {
            if (list1->val < list2->val) {
                t = t->next = list1;
                list1 = list1->next;
            } else {
                t = t->next = list2;
                list2 = list2->next;
            }
        }

        t->next = list1 ? list1 : list2;
        return head.next;
    }

    ListNode *getMid(ListNode *head) {
        ListNode *fast, *slow;
        fast = slow = head;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        fast = slow->next;
        slow->next = nullptr;
        return fast;
    }
};