給定一個鏈結串列的頭節點
head和一個值x，將串列分區使得所有小於x的節點排在大於等於x的節點前面，且保持各區內節點的相對順序不變。
Example:
Input: head = [1,4,3,2,5,2], x = 3 Output: [1,2,2,4,3,5]
Intuition
TIP
核心思路：建立兩個獨立的鏈結串列分別收集小於 x 和大於等於 x 的節點，最後串接。
- 類似 Quick Sort 的 partition，但需要保持穩定性（相對順序不變）
- 用兩個 dummy head 分別建立「小」和「大」兩條鏈結串列
- 遍歷完後將兩條串列串接起來
Approaches
1. Collect Values then Rebuild — O(n) / O(n)
- Idea: 掃一遍把
< x與>= x的值分別收集，再依序建成新串列。直觀但多花 O(n) 空間 - Time:
O(n) - Space:
O(n)- 兩個值清單與新節點
class Solution {
fun partition(head: ListNode?, x: Int): ListNode? {
val less = ArrayList<Int>()
val ge = ArrayList<Int>()
var cur = head
while (cur != null) {
if (cur.`val` < x) less.add(cur.`val`) else ge.add(cur.`val`)
cur = cur.next
}
val dummy = ListNode(0)
var tail = dummy
for (v in less) { tail.next = ListNode(v); tail = tail.next!! }
for (v in ge) { tail.next = ListNode(v); tail = tail.next!! }
return dummy.next
}
}⭐ 2. Two Dummy Lists (in-place, space-saving) — O(n) / O(1)
- Idea: 建立 small 和 large 兩個 dummy 鏈結串列，遍歷原串列將每個節點分配到對應的串列，最後串接
- Time:
O(n) - Space:
O(1)- 只是重新接指針，不建立新節點
class Solution {
fun partition(head: ListNode?, x: Int): ListNode? {
val smallDummy = ListNode(0)
val largeDummy = ListNode(0)
var small: ListNode = smallDummy
var large: ListNode = largeDummy
var curr = head
while (curr != null) {
if (curr.`val` < x) {
small.next = curr
small = small.next!!
} else {
large.next = curr
large = large.next!!
}
curr = curr.next
}
// 串接兩條串列
large.next = null // 重要！避免形成環
small.next = largeDummy.next
return smallDummy.next
}
}WARNING
最後必須將 large 的尾端設為 null，否則可能形成環。這是因為 large 的最後一個節點的 next 可能仍然指向 small 串列中的某個節點。
🔑 Takeaways
- Pattern: 將鏈結串列依條件分成多條再串接，是處理 partition/分組問題的通用技巧
- Key trick: 分離後重新串接時，務必將最後一個節點的 next 設為 null，避免環的產生