148. Sort List

Medium

Description

給定一個鏈結串列的頭節點 head，將其排序後回傳。要求時間複雜度 O(n log n)，空間複雜度 O(1)。

Example:

Input: head = [4,2,1,3] Output: [1,2,3,4]

Intuition#

核心思路：鏈結串列最適合 Merge Sort，因為合併兩個有序串列是 O(1) 空間的天然操作。

陣列的 Merge Sort 需要額外空間來合併，但鏈結串列的合併只需改指針
分割：用快慢指針找中點，斷開為兩半
合併：與 LC 21 Merge Two Sorted Lists 相同

Approaches#

1: Top-Down Merge Sort (Recursive)#

概念: 遞迴地將串列從中點分割，排序後合併
時間複雜度: O(n log n)
空間複雜度: O(log n) - 遞迴堆疊深度

class Solution {
    fun sortList(head: ListNode?): ListNode? {
        if (head?.next == null) return head

        // 快慢指針找中點（取前半段的最後一個節點）
        var slow = head
        var fast = head.next
        while (fast?.next != null) {
            slow = slow?.next
            fast = fast.next?.next
        }

        // 斷開為兩半
        val mid = slow?.next
        slow?.next = null

        // 遞迴排序
        val left = sortList(head)
        val right = sortList(mid)

        // 合併
        return merge(left, right)
    }

    private fun merge(l1: ListNode?, l2: ListNode?): ListNode? {
        val dummy = ListNode(0)
        var curr: ListNode = dummy
        var p1 = l1
        var p2 = l2

        while (p1 != null && p2 != null) {
            if (p1.`val` <= p2.`val`) {
                curr.next = p1
                p1 = p1.next
            } else {
                curr.next = p2
                p2 = p2.next
            }
            curr = curr.next!!
        }
        curr.next = p1 ?: p2
        return dummy.next
    }
}

⭐2: Bottom-Up Merge Sort (Iterative)#

概念: 從大小 1 開始，逐步合併相鄰的子串列，大小依次翻倍，真正的 O(1) 空間
時間複雜度: O(n log n)
空間複雜度: O(1) - 純迭代

class Solution {
    fun sortList(head: ListNode?): ListNode? {
        if (head?.next == null) return head

        // 計算長度
        var length = 0
        var curr = head
        while (curr != null) {
            length++
            curr = curr.next
        }

        val dummy = ListNode(0)
        dummy.next = head
        var size = 1

        while (size < length) {
            var prev: ListNode = dummy
            var cur = dummy.next

            while (cur != null) {
                // 取第一段 (size 個節點)
                val left = cur
                var i = 1
                while (i < size && cur?.next != null) {
                    cur = cur.next
                    i++
                }

                // 取第二段
                val right = cur?.next
                cur?.next = null  // 斷開第一段
                cur = right
                i = 1
                while (i < size && cur?.next != null) {
                    cur = cur.next
                    i++
                }

                // 記住剩餘部分
                val remaining = cur?.next
                cur?.next = null  // 斷開第二段

                // 合併兩段
                prev.next = merge(left, right)

                // prev 移到合併後的尾端
                while (prev.next != null) {
                    prev = prev.next!!
                }

                cur = remaining
            }
            size *= 2
        }

        return dummy.next
    }

    private fun merge(l1: ListNode?, l2: ListNode?): ListNode? {
        val dummy = ListNode(0)
        var curr: ListNode = dummy
        var p1 = l1
        var p2 = l2

        while (p1 != null && p2 != null) {
            if (p1.`val` <= p2.`val`) {
                curr.next = p1
                p1 = p1.next
            } else {
                curr.next = p2
                p2 = p2.next
            }
            curr = curr.next!!
        }
        curr.next = p1 ?: p2
        return dummy.next
    }
}

找中點時 fast 應從 head.next 開始（而非 head），確保分割的前半段不會多出一個節點，避免無限遞迴。

🔑 Takeaways#

Pattern: 鏈結串列排序首選 Merge Sort，因為合併有序串列只需 O(1) 空間修改指針
關鍵技巧: Top-Down 容易寫但有 O(log n) 遞迴空間；Bottom-Up 是真正 O(1) 空間但實作較複雜