Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 148. Sort List

---

參考資訊：
https://www.cnblogs.com/grandyang/p/4249905.html

題目：


解答：

/**
 * 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) {
        if (!head || !head->next) {
            return head;
        }

        ListNode *pre = nullptr;
        ListNode *slow = head;
        ListNode *fast = head;

        while (fast && fast->next) {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr;

        auto merge = [&](this auto&& merge, ListNode* l1, ListNode* l2) -> ListNode* {
            ListNode d0;
            ListNode *cur = &d0;

            while (l1 && l2) {
                if (l1->val < l2->val) {
                    cur->next = l1;
                    l1 = l1->next;
                }
                else {
                    cur->next = l2;
                    l2 = l2->next;
                }

                cur = cur->next;
            }

            if (l1) cur->next = l1;
            if (l2) cur->next = l2;

            return d0.next;
        };

        return merge(sortList(head), sortList(slow));
    }
};