文章目錄
- 92. 反轉鏈表 II
- 題目描述
- 示例 1：
- 示例 2：
- 提示：
- 進階： 你可以使用一趟掃描完成反轉嗎？
- 解題思路
- 問題深度分析
- 核心思想對比
- 算法流程圖
- 複雜度分析
- 關鍵邊界與陷阱
- 方法與代碼要點（Go）
- 測試用例設計
- 實戰技巧
- 完整題解代碼
92. 反轉鏈表 II
題目描述
給你單鏈表的頭指針 head 和兩個整數 left 和 right ，其中 left <= right 。請你反轉從位置 left 到位置 right 的鏈表節點，返回 反轉後的鏈表 。
示例 1：
輸入：head = [1,2,3,4,5], left = 2, right = 4
輸出：[1,4,3,2,5]
示例 2：
輸入：head = [5], left = 1, right = 1
輸出：[5]
提示：
- 鏈表中節點數目為 n
- 1 <= n <= 500
- -500 <= Node.val <= 500
- 1 <= left <= right <= n
進階： 你可以使用一趟掃描完成反轉嗎？
解題思路
問題深度分析
本題要求在單鏈表中僅反轉[left, right]區間節點，其他部分保持原相對順序，時間O(n)、空間O(1)的一趟掃描是最優思路。核心在於：精確定位邊界、斷開/接回指針、在區間內進行原地反轉。
- 關鍵指針：
pre（指向left前一個結點）、leftNode（left處結點）、rightNode（right處結點）、rightNext（right後一個結點）。 - 一趟掃描常用“頭插法”在區間內原地重排；或使用常規反轉再接回。
核心思想對比
- 方法一（頭插法一趟掃描，最優）：固定
pre，每次把leftNode後面的結點摘下，插到pre之後，實現區間內前插，O(1)空間，O(n)時間。 - 方法二（常規反轉再接回）：先走到
pre與rightNext，斷開[left,right]，常規反轉，再接回，思路直觀。 - 方法三（遞歸：反轉前N個 + 偏移）：將問題轉為“反轉鏈表前N個”子問題，向右偏移left-1次，遞歸優雅但實現需小心邊界。
- 方法四（棧/數組輔助）：將區間內節點壓棧後再彈出拼接，易寫但需O(k)額外空間（k=right-left+1）。
算法流程圖
主流程（以頭插法為例）
啞結點dummy->head
定位pre到left前一位
leftNode=pre.next
i從0到right-left-1
取出next := leftNode.next
leftNode.next = next.next
next.next = pre.next
pre.next = next
完成, 返回dummy.next
常規反轉+接回
dummy->head
找到pre與rightNode
rightNext=rightNode.next
斷開pre.next..rightNode子鏈
反轉子鏈
pre.next=反轉後的頭
原leftNode.next=rightNext
返回dummy.next
遞歸思路（反轉前N個）
graph TD
A[reverseBetween(head,left,right)] --> B{left==1?}
B -->|是| C[reverseN(head, right)]
B -->|否| D[head.next = reverseBetween(head.next,left-1,right-1)]
D --> E[返回head]複雜度分析
- 時間複雜度：四種方法均為O(n)，n為鏈表長度。
- 空間複雜度：
- 頭插法與常規反轉：O(1)
- 遞歸：O(right-left+1) 遞歸棧
- 棧法：O(right-left+1) 額外空間
關鍵邊界與陷阱
- left==right：無需操作直接返回。
- left==1：
pre為dummy，注意連接。 - 只有一個節點/空鏈表：直接返回。
- 區間在尾部：
rightNext可能為nil，接回時謹慎。 - 指針順序：先保存
next再修改指針，避免丟鏈。
方法與代碼要點（Go）
- 方法一：頭插法一趟掃描（推薦最優）
- 固定
pre與leftNode，把leftNode後面的節點依次插到pre後面。
- 方法二：常規反轉子鏈後接回
- 先切出子鏈段，再常規反轉，然後兩端接回。
- 方法三：遞歸reverseN
reverseBetween(head,l,r)：若l==1，調用reverseN(head,r)；否則head.next = reverseBetween(head.next,l-1,r-1)。
- 方法四：棧輔助
- 遍歷區間壓棧，隨後彈棧重建區間，最後接回。
測試用例設計
- [1,2,3,4,5], left=2, right=4 -> [1,4,3,2,5]
- [5], left=1, right=1 -> [5]
- [1,2,3], left=1, right=3 -> [3,2,1]
- [1,2,3,4], left=3, right=4 -> [1,2,4,3]
- [1,2], left=1, right=2 -> [2,1]
- 邊界：空/單節點/left==right/區間含尾部
實戰技巧
- 啞結點
dummy極大簡化頭部操作。 - 指針改動順序：保存next -> 斷開 -> 插入/反轉 -> 接回。
- 模板化書寫，減少出錯。
完整題解代碼
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
// =========================== 方法一：頭插法一趟掃描（最優） ===========================
func reverseBetween1(head *ListNode, left int, right int) *ListNode {
if head == nil || left == right {
return head
}
dummy := &ListNode{Next: head}
pre := dummy
for i := 1; i < left; i++ {
pre = pre.Next
}
leftNode := pre.Next
for i := 0; i < right-left; i++ {
next := leftNode.Next
leftNode.Next = next.Next
next.Next = pre.Next
pre.Next = next
}
return dummy.Next
}
// =========================== 方法二：常規反轉子鏈後接回 ===========================
func reverseBetween2(head *ListNode, left int, right int) *ListNode {
if head == nil || left == right {
return head
}
dummy := &ListNode{Next: head}
pre := dummy
for i := 1; i < left; i++ {
pre = pre.Next
}
rightNode := pre
for i := 0; i < right-left+1; i++ {
rightNode = rightNode.Next
}
rightNext := rightNode.Next
// 切下子鏈
leftNode := pre.Next
rightNode.Next = nil
// 反轉子鏈
revHead := reverseList(leftNode)
// 接回
pre.Next = revHead
leftNode.Next = rightNext
return dummy.Next
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
for head != nil {
next := head.Next
head.Next = prev
prev = head
head = next
}
return prev
}
// =========================== 方法三：遞歸（reverseN + 偏移） ===========================
var successor *ListNode
func reverseBetween3(head *ListNode, left int, right int) *ListNode {
if left == 1 {
return reverseN(head, right)
}
head.Next = reverseBetween3(head.Next, left-1, right-1)
return head
}
func reverseN(head *ListNode, n int) *ListNode {
if n == 1 {
successor = head.Next
return head
}
last := reverseN(head.Next, n-1)
head.Next.Next = head
head.Next = successor
return last
}
// =========================== 方法四：棧輔助 ===========================
func reverseBetween4(head *ListNode, left int, right int) *ListNode {
if head == nil || left == right {
return head
}
dummy := &ListNode{Next: head}
pre := dummy
for i := 1; i < left; i++ {
pre = pre.Next
}
// 收集區間節點
stack := []*ListNode{}
node := pre.Next
for i := left; i <= right; i++ {
stack = append(stack, node)
node = node.Next
}
rightNext := node
// 從棧彈出重建
for len(stack) > 0 {
n := stack[len(stack)-1]
stack = stack[:len(stack)-1]
pre.Next = n
pre = pre.Next
}
pre.Next = rightNext
return dummy.Next
}
// =========================== 工具方法與測試 ===========================
func buildList(vals []int) *ListNode {
if len(vals) == 0 {
return nil
}
head := &ListNode{Val: vals[0]}
cur := head
for i := 1; i < len(vals); i++ {
cur.Next = &ListNode{Val: vals[i]}
cur = cur.Next
}
return head
}
func toSlice(head *ListNode) []int {
var res []int
for head != nil {
res = append(res, head.Val)
head = head.Next
}
return res
}
func equalSlice(a, b []int) bool {
if len(a) != len(b) {
return false
}
for i := range a {
if a[i] != b[i] {
return false
}
}
return true
}
func runTests(methodName string, f func(*ListNode, int, int) *ListNode) int {
tests := []struct {
in []int
l, r int
want []int
label string
}{
{[]int{1, 2, 3, 4, 5}, 2, 4, []int{1, 4, 3, 2, 5}, "mid range"},
{[]int{5}, 1, 1, []int{5}, "single"},
{[]int{1, 2, 3}, 1, 3, []int{3, 2, 1}, "all"},
{[]int{1, 2, 3, 4}, 3, 4, []int{1, 2, 4, 3}, "tail"},
{[]int{1, 2}, 1, 2, []int{2, 1}, "two"},
{[]int{1, 2, 3, 4, 5}, 3, 3, []int{1, 2, 3, 4, 5}, "no-op"},
}
pass := 0
for i, tc := range tests {
head := buildList(tc.in)
out := f(head, tc.l, tc.r)
s := toSlice(out)
ok := equalSlice(s, tc.want)
status := "✅"
if !ok {
status = "❌"
}
fmt.Printf(" 測試%d(%s): %s\n", i+1, tc.label, status)
if !ok {
fmt.Printf(" 輸入: %v, left=%d, right=%d\n", tc.in, tc.l, tc.r)
fmt.Printf(" 輸出: %v\n", s)
fmt.Printf(" 期望: %v\n", tc.want)
} else {
pass++
}
}
fmt.Printf(" 通過: %d/%d\n\n", pass, len(tests))
return pass
}
func main() {
fmt.Println("=== LeetCode 92: 反轉鏈表 II ===\n")
methods := []struct {
name string
fn func(*ListNode, int, int) *ListNode
}{
{"頭插法一趟掃描（最優）", reverseBetween1},
{"常規反轉後接回", reverseBetween2},
{"遞歸（reverseN）", reverseBetween3},
{"棧輔助", reverseBetween4},
}
for _, m := range methods {
fmt.Printf("方法：%s\n", m.name)
runTests(m.name, m.fn)
}
}