給定一個鏈結串列的頭節點
head，將其排序後回傳。要求時間複雜度O(n log n)，空間複雜度O(1)。
Example:
Input: head = [4,2,1,3] Output: [1,2,3,4]
Intuition
TIP
核心思路：鏈結串列最適合 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)
- Idea: 遞迴地將串列從中點分割，排序後合併
- Time:
O(n log n) - Space:
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) — O(n log n) / O(1)
- Idea: 從大小 1 開始，逐步合併相鄰的子串列，大小依次翻倍，真正的 O(1) 空間
- Time:
O(n log n) - Space:
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
}
}WARNING
找中點時 fast 應從 head.next 開始（而非 head），確保分割的前半段不會多出一個節點，避免無限遞迴。
🔑 Takeaways
- Pattern: 鏈結串列排序首選 Merge Sort，因為合併有序串列只需 O(1) 空間修改指針
- Key trick: Top-Down 容易寫但有 O(log n) 遞迴空間；Bottom-Up 是真正 O(1) 空間但實作較複雜