C++实现LeetCode(92.倒置链表之二)

前言

LeetCode 92 题「Reverse Linked List II」要求：给定单链表的头指针和两个整数left、right（1 ≤ left ≤ right ≤ n），把链表中从第left个结点到第right个结点的部分反转，其余部分保持原样，返回新的头指针。和第 206 题「反转整个链表」相比，这道题的难点在于「只反转一段」以及「把反转后的子链表重新接回原链表」。

常见的错误有三种：一是不用哨兵结点（dummy node），导致left == 1时要单独处理头指针；二是反转后忘记把子链表的两端接回去，造成断链或环；三是循环次数算错，多反转或少反转一个结点。本文用「头插法」在 O(n) 时间、O(1) 空间内完成，并给出逐步推演。

代码以 C++17 为基准，结点使用裸指针，这是链表题最常见的写法；文末会说明工程代码中如何用std::unique_ptr表达所有权。

一、链表结点与哨兵结点

// 适用于 C++17
struct ListNode {
int val;
ListNode* next;
explicit ListNode(int x) : val(x), next(nullptr) {}
};

explicit防止ListNode n = 5;这种隐式转换。成员next在构造函数里显式置空，避免未初始化指针。

哨兵结点（dummy node）是一个不存储实际数据的辅助结点，它的next指向真正的头结点。引入它之后，「头结点也可能被反转」这一特殊情况就变成了普通情况：无论left是 1 还是其他值，我们都可以先找到「反转区间的前一个结点」，统一处理。

// 适用于 C++17
ListNode dummy(0);
dummy.next = head;
ListNode* prev = &dummy;
for (int i = 1; i < left; ++i) {
prev = prev->next;
}

循环结束时，prev指向第left - 1个结点（left == 1时就是dummy）。prev->next是反转区间的第一个结点，记作cur。

注意ListNode dummy(0);是栈上的对象，函数返回时自动销毁。我们只返回dummy.next，不返回&dummy，所以不存在悬垂指针。

二、头插法反转区间

反转区间[left, right]的长度是right - left + 1。设cur = prev->next，它始终指向反转后区间的「尾部」（也就是原来区间的第一个结点）。每次把cur的下一个结点nxt摘下来，插到prev的后面：

nxt = cur->next;
cur->next = nxt->next; // 从原位置摘下 nxt
nxt->next = prev->next; // nxt 指向当前区间头部
prev->next = nxt; // prev 指向新的区间头部

执行right - left次，整个区间就反转完成。

为什么是right - left次而不是right - left + 1次？因为区间有right - left + 1个结点，其中第一个结点cur已经在位置上，只需要把后面的right - left个结点依次插到它前面。每插入一个，区间头部就前移一位，最终cur变成区间尾部。

// 适用于 C++17
ListNode* cur = prev->next;
for (int i = 0; i < right - left; ++i) {
ListNode* nxt = cur->next;
cur->next = nxt->next;
nxt->next = prev->next;
prev->next = nxt;
}
return dummy.next;

这个写法有一个容易忽略的优点：它不修改prev和cur本身，只修改它们指向的结点的next。prev始终是区间前一个结点，cur始终是区间尾部，循环结束时不需要额外的重连操作——区间两端的连接在每次插入时已经维护好了。

三、逐步推演

以链表1 → 2 → 3 → 4 → 5、left = 2、right = 4为例。初始prev指向结点 1，cur指向结点 2，循环执行4 - 2 = 2次。

最终dummy.next指向 1，整条链表是1 → 4 → 3 → 2 → 5。区间[2,4]原为2,3,4，反转为4,3,2，其余不变，正确。

再看left = 1、right = 3的情况：prev是dummy，cur是结点 1。第 1 轮把 2 插到 dummy 后面，链表变成dummy → 2 → 1 → 3 → 4...；第 2 轮把 3 插到 dummy 后面，变成dummy → 3 → 2 → 1 → 4...。返回dummy.next即结点 3，头指针正确更新。

再看left == right的情况：循环次数为 0，链表不变，返回原头指针。这符合「反转长度为 1 的区间等于不变」的语义。

四、边界与不变量

写链表题时，明确不变量（invariant）比记住代码更有用。头插法的循环不变量是：

• 
  
• prev指向区间前一个结点，固定不变。
• 
  
• prev->next指向当前已反转部分的头结点。
• 
  
• cur指向当前已反转部分的尾结点，也就是原区间的第一个结点。
• 
  
• cur->next指向尚未反转部分的第一个结点。
• 
  

每轮循环把cur->next（即nxt）摘下来插到prev后面，上述四条仍然成立，只是已反转部分多了一个结点、未反转部分少了一个结点。循环结束时未反转部分为空，区间反转完成，且cur->next自动指向区间后的第一个结点（原链表的第right + 1个结点），不需要手动重连。

这个「不需要手动重连」是头插法相对于「先切断、反转、再拼接」的优势。后者需要保存四个指针（区间前、区间头、区间尾、区间后），一旦某个指针保存错，就会出现断链或环。

需要特别注意的边界：

1. 
   
2. left == 1：由dummy兜住，不需要改head变量。
3. 
   
4. left == right：循环 0 次，直接返回。
5. 
   
6. right == n：cur->next最终为nullptr，循环中nxt不会是空指针（因为循环次数不超过区间长度减一），安全。
7. 
   
8. 空链表：题目通常保证n ≥ 1；若不允许，需在函数开头判head == nullptr。
9. 
   

五、完整示例

// 适用于 C++17
#include <iostream>
#include <vector>

struct ListNode {
int val;
ListNode* next;
explicit ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseBetween(ListNode* head, int left, int right) {
if (head == nullptr || left == right) return head;

ListNode dummy(0);
dummy.next = head;

ListNode* prev = &dummy;
for (int i = 1; i < left; ++i) {
prev = prev->next;
}

ListNode* cur = prev->next;
for (int i = 0; i < right - left; ++i) {
ListNode* nxt = cur->next;
cur->next = nxt->next;
nxt->next = prev->next;
prev->next = nxt;
}

return dummy.next;
}

ListNode* build(const std::vector<int>& values) {
ListNode dummy(0);
ListNode* tail = &dummy;
for (int v : values) {
tail->next = new ListNode(v);
tail = tail->next;
}
return dummy.next;
}

void destroy(ListNode* head) {
while (head != nullptr) {
ListNode* next = head->next;
delete head;
head = next;
}
}

void print(ListNode* head) {
while (head != nullptr) {
std::cout << head->val;
if (head->next != nullptr) std::cout << " -> ";
head = head->next;
}
std::cout << '\n';
}

int main() {
ListNode* head = build({1, 2, 3, 4, 5});
head = reverseBetween(head, 2, 4);
print(head); // 按标准语义应为 1 -> 4 -> 3 -> 2 -> 5
destroy(head);
return 0;
}

build和destroy是配套的：build里每个new都在destroy里有对应的delete。如果只写build不写destroy，程序结束前不会崩溃，但这是内存泄漏；在长时间运行的服务里会累积。工程代码更推荐用std::unique_ptr<ListNode>和std::make_unique，让所有权自动管理。

六、用智能指针表达所有权

如果不想手写destroy，可以把结点定义改成：

// 适用于 C++17
#include <memory>

struct ListNode {
int val;
std::unique_ptr<ListNode> next;
explicit ListNode(int x) : val(x), next(nullptr) {}
};

这样整条链表的所有权是唯一的、递归的，头指针析构时整条链自动释放。但反转操作的代码会变得啰嗦，因为std::unique_ptr不能拷贝，移动和交换需要小心处理。面试和算法题里通常仍用裸指针，工程代码里则优先用智能指针或标准容器。两种写法没有对错，关键是不要在同一个项目里混用两套所有权约定。

常见坑点

1. 不用哨兵结点，单独处理 left == 1

❌ 在left == 1分支里手动更新head，其余分支另一套逻辑，容易漏改。

✅ 用dummy.next = head，统一返回dummy.next。

2. 循环次数写成 right - left + 1

❌ 多反转一个结点，区间尾部被带到区间外。

✅ 循环right - left次；区间有right - left + 1个结点，第一个已在位。

3. 反转后忘记重连

❌ 先切断子链表再反转，最后只接回一端，另一端悬空。

✅ 用头插法，每轮都维护prev->next和cur->next，结束时自然接好。

4. 先移动 prev 再保存 cur

❌prev = prev->next; ListNode* cur = prev->next;导致prev指向区间第一个结点而不是前一个。

✅ 先让prev走到第left - 1个结点，再取cur = prev->next。

5. 返回了 dummy 的地址

❌return &dummy;——dummy是局部对象，函数返回后悬垂。

✅return dummy.next;。

6. 忘记处理 left == right

❌ 循环条件写成i <= right - left，多执行一次，把区间外的结点也卷进来。

✅ 循环i < right - left；或开头直接if (left == right) return head;。

7. 在循环里修改 cur 的指向后还用它找下一个

❌ 先cur = cur->next再取nxt，顺序错乱。

✅ 每轮开头先保存ListNode* nxt = cur->next;，再修改指针。

8. 释放链表时先 delete 再读 next

❌delete head; head = head->next;—— 释放后使用，UB。

✅ 先ListNode* next = head->next;，再delete head;，最后head = next;。

总结

区间反转的代码只有十来行，但每一行都在改指针，任何一处顺序错误都会导致断链或成环。把「prev 固定、cur 是尾、nxt 是待插结点」这三个角色记牢，再配合哨兵结点消除头指针的特殊情况，这道题就能一次写对。