Description
給定一個鏈結串列的頭節點
head，以及兩個整數left和right（left <= right），反轉從位置left到right的節點，回傳反轉後的頭節點。位置從 1 開始計數。
Example:
Input: head = [1,2,3,4,5], left = 2, right = 4 Output: [1,4,3,2,5]
Intuition#
核心思路：定位到反轉區間的前一個節點，然後用頭插法（或標準反轉）將區間內的節點反轉。
- 需要找到 left 之前的節點（prevLeft）和反轉區間的起始節點
- 反轉區間內的節點後，重新連接前後部分
- 使用 dummy head 處理 left == 1 的邊界情況
Approaches#
1: Standard Reverse Sublist#
- 概念: 先定位到反轉區間，將區間內的節點用標準三指針法反轉，最後重新連接
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun reverseBetween(head: ListNode?, left: Int, right: Int): ListNode? {
val dummy = ListNode(0)
dummy.next = head
// 找到 left 的前一個節點
var prev: ListNode? = dummy
for (i in 1 until left) {
prev = prev?.next
}
// 反轉 left 到 right 的節點
var curr = prev?.next
var reversePrev: ListNode? = null
for (i in 0..right - left) {
val next = curr?.next
curr?.next = reversePrev
reversePrev = curr
curr = next
}
// 重新連接
prev?.next?.next = curr // 反轉區間的原第一個節點（現在是最後）連到 right+1
prev?.next = reversePrev // left 的前一個節點連到反轉後的頭（原 right 節點）
return dummy.next
}
}⭐2: Head Insertion (One Pass)#
- 概念: 定位到 left 前的節點後，不斷將後面的節點用「頭插法」插入到反轉區間的最前面
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun reverseBetween(head: ListNode?, left: Int, right: Int): ListNode? {
val dummy = ListNode(0)
dummy.next = head
// 找到 left 的前一個節點
var prev: ListNode? = dummy
for (i in 1 until left) {
prev = prev?.next
}
// curr 固定在原 left 位置，不斷把 curr.next 插到 prev 後面
val curr = prev?.next
for (i in 0 until right - left) {
val moveNode = curr?.next
curr?.next = moveNode?.next
moveNode?.next = prev?.next
prev?.next = moveNode
}
return dummy.next
}
}頭插法中 curr 始終指向原 left 節點（它會逐漸移到反轉區間的末尾），不要移動 curr 指針。
🔑 Takeaways#
- Pattern: 區間反轉是 LC 206 的延伸，也是 k-Group Reverse 的基礎
- 關鍵技巧: 頭插法只需一次遍歷，且不需要在反轉後手動重新連接前後部分，非常優雅