MediumRating 1636
148. Sort List
linked-listtwo-pointersdivide-and-conquersortingmerge-sort
解題說明
Sort List
題目描述：給定一個鏈結串列的頭節點，請在 O(n log n) 時間複雜度、O(1) 輔助空間（不含遞迴堆疊）的條件下對其排序並回傳頭節點。
解題思路：時間複雜度要求 O(n log n) 且需在鏈結串列上操作，最適合的演算法是歸併排序（Merge Sort）——它在鏈結串列上可以實現 O(1) 的合併（無需額外陣列），且分治的遞迴深度為 O(log n)。
整體流程分三步：
- 找中點：使用快慢指標（slow/fast pointer）找到串列中點，將串列一分為二。注意需將左半段尾節點的
next設為nullptr，避免兩段相連。 - 遞迴排序：對左右兩半各自遞迴排序。
- 合併：將兩個已排序的串列合併為一個有序串列，這與「合併兩個有序鏈結串列」問題完全相同。
遞迴版本的空間複雜度為 O(log n)（遞迴堆疊），若要達到嚴格 O(1) 空間，需改用迭代式由下而上的歸併排序。
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 歸併排序共 log n 層，每層合併操作總共掃描 n 個節點。
空間複雜度：O(log n) — 遞迴呼叫的堆疊深度為 log n（樹高）。若改用迭代式由下而上歸併排序，可達到嚴格 O(1) 輔助空間（不含輸入鏈結串列本身）。
虛擬碼
1. sortList(head):
a. If head is null or head.next is null, return head (base case)
b. mid = getMiddle(head)
c. rightHead = mid.next; set mid.next = null (split list)
d. left = sortList(head)
e. right = sortList(rightHead)
f. Return merge(left, right)
2. getMiddle(head):
a. slow = head, fast = head.next
b. While fast != null and fast.next != null:
- slow = slow.next, fast = fast.next.next
c. Return slow (node just before midpoint)
3. merge(l1, l2):
a. Create dummy node; tail = dummy
b. While l1 != null and l2 != null:
- Append the smaller head to tail; advance that pointer and tail
c. Attach remaining non-null list to tail
d. Return dummy.next其他解法
方法一：迭代式由下而上歸併排序（Bottom-Up Merge Sort） 從長度為 1 的子串列開始，依次合併長度為 1、2、4、8…的相鄰段落，直到整個串列有序。時間複雜度 O(n log n)，空間複雜度 O(1)（嚴格無遞迴堆疊），是滿足題目 O(1) 空間要求的真正最優解，但實作較複雜，需要精確維護指標。
方法二：轉換為陣列後排序
將鏈結串列所有值存入 vector，排序後再寫回節點。時間複雜度 O(n log n)，空間複雜度 O(n)。實作最簡單，但不滿足題目的 O(1) 空間要求，也不展示鏈結串列原地操作的技巧。
延伸思考
- 題目要求 O(1) 空間，但遞迴解的堆疊深度為 O(log n)。請描述迭代式由下而上歸併排序的核心思路，並說明它如何避免遞迴堆疊？
- 若改為對**雙向鏈結串列（Doubly Linked List）**排序，演算法需要哪些調整？是否有可以利用的額外性質？
- 對鏈結串列使用快速排序（Quick Sort）是否實際可行？請分析其在最壞情況下的時間複雜度，以及與歸併排序相比的優劣。