86. Partition List
MediumDescription
給定一個鏈結串列的頭節點
head和一個值x，將串列分區使得所有小於x的節點排在大於等於x的節點前面，且保持各區內節點的相對順序不變。
Example:
Input: head = [1,4,3,2,5,2], x = 3 Output: [1,2,2,4,3,5]
Intuition#
核心思路：建立兩個獨立的鏈結串列分別收集小於 x 和大於等於 x 的節點，最後串接。
- 類似 Quick Sort 的 partition，但需要保持穩定性（相對順序不變）
- 用兩個 dummy head 分別建立「小」和「大」兩條鏈結串列
- 遍歷完後將兩條串列串接起來
Approaches#
⭐1: Two Dummy Lists#
- 概念: 建立 small 和 large 兩個 dummy 鏈結串列，遍歷原串列將每個節點分配到對應的串列，最後串接
- 時間複雜度:
O(n) - 空間複雜度:
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
}
}最後必須將 large 的尾端設為 null，否則可能形成環。這是因為 large 的最後一個節點的 next 可能仍然指向 small 串列中的某個節點。
🔑 Takeaways#
- Pattern: 將鏈結串列依條件分成多條再串接，是處理 partition/分組問題的通用技巧
- 關鍵技巧: 分離後重新串接時，務必將最後一個節點的 next 設為 null，避免環的產生