Leetcode 148. Sort List

Sort List : 此題的意思就是給你一個link list，要把它排序由小到大，而且要在時間複雜度O(n logn)之下完成，並且空間複雜度要在O(1)之下

第一種解法 : Merge Sort (Top-Down)

利用快慢指針來求解，經過遞迴慢指針會找到中間的節點，快指針會找到最後的節點，之後把兩個指針切開分成兩個list，之後分別去遞歸排序兩個list，最後再merge起來

時間複雜度 : O(n logn)

空間複雜度: O(logn)

Python

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        # 找到鍊表的中間節點
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None  # 斷開鍊接

        # 遞規排序
        left = self.sortList(head)
        right = self.sortList(mid)

        # 合併有序鍊表
        dummy = ListNode(0)
        cur = dummy
        while left and right:
            if left.val < right.val:
                cur.next = left
                left = left.next
            else:
                cur.next = right
                right = right.next
            cur = cur.next
        cur.next = left or right
        return dummy.next

C++

歸併排序:

找到鍊錶的中間節點，可以使用快慢指針來實現。 對左右兩個子鍊錶分別遞歸排序。 將兩個有序的子鍊錶進行合併。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head; // 邊界條件
        ListNode *slow = head, *fast = head->next;
        while (fast && fast->next) { // 找到中間節點
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *mid = slow->next;
        slow->next = nullptr; // 斷開鍊表

        ListNode *left = sortList(head); // 左半邊排序
        ListNode *right = sortList(mid); // 右半邊排序

        // 合併
        ListNode dummy(0);
        ListNode *cur = &dummy;
        while (left && right) {
            if (left->val < right->val) {
                cur->next = left;
                left = left->next;
            } else {
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        cur->next = left ? left : right;
        return dummy.next;
    }
};