链表进阶核心 | LeetCode 92 区间反转：吃透递归反转与哨兵技巧

Ne0inhk

— 9 min read
链表进阶核心 | LeetCode 92 区间反转：吃透递归反转与哨兵技巧

✨链表进阶核心 | LeetCode 92 区间反转：吃透递归反转与哨兵技巧🎯

视频地址

因为想更好的为大佬服务，制作了同步视频，这是Bilibili的视频地址

链表反转是数据结构与算法中的经典高频考点，从基础的全链表反转，到反转前n个节点，再到进阶的区间反转，层层递进。本文将以LeetCode 92. 反转链表 II为核心，从基础的「反转前n个节点」递归实现讲起，结合虚拟头节点神器，手把手拆解区间反转的解题逻辑，带你彻底掌握链表递归反转的核心思想！

🚀 开篇引论：链表反转的进阶之路

链表是一种线性、离散存储的数据结构，节点之间通过指针关联，无法像数组一样随机访问，这也让链表反转成为了考察指针操作与递归思维的最佳题型。

LeetCode 92 区间反转问题，并非孤立的算法题，而是**「反转前n个节点」**的进阶应用。我们的解题思路非常清晰：先攻克基础的前n节点反转，再将区间反转问题拆解为基础问题的组合，化繁为简，轻松破解难题。

🔄 基础筑基：链表【前n个节点】递归反转

在解决区间反转之前，我们必须先实现一个核心工具函数：反转链表的前n个节点，这是解题的核心基石。

1. 函数定义与核心功能

我们定义递归函数 reverseN，功能如下：

  • 函数签名：ListNode* reverseN(ListNode* head, int n)
  • 核心功能：反转以head为头节点的链表的前n个节点，返回反转后的新链表头节点；剩余未反转节点保持原顺序。

2. 递归实现思路拆解

递归的核心是分解子问题 + 终止条件 + 回溯调整指针，严格遵循以下逻辑：

  1. 终止条件：当n == 1时，说明已经找到待反转的最后一个节点，直接返回当前节点（新头节点）；
  2. 递归子问题：记录当前节点的下一个节点为tail，递归调用reverseN反转head.next开头的n-1个节点；
  3. 回溯调整指针：将当前头节点指向tail的后继节点，再将tail指向当前头节点，完成局部反转；
  4. 返回结果：最终返回递归得到的新头节点。

3. 直观调用示例

我们以链表 1->2->3->4 为例，通过表格直观展示函数效果：

原链表结构输入参数n反转后链表结构
1->2->3->422->1->3->4
1->2->3->433->2->1->4

4. 关键代码实现（C++）与详解

 // 链表节点定义（通用） struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; // 核心函数：反转链表前n个节点（递归实现） ListNode* reverseN(ListNode* head, int n) { // 终止条件：n=1，到达待反转的最后一个节点，直接返回 if (n == 1) { return head; } // 记录当前节点的下一个节点（待反转的子链表头） ListNode* tail = head->next; // 递归反转：反转head.next的前n-1个节点，得到新头节点 ListNode* newHead = reverseN(head->next, n - 1); // 指针调整：当前头节点指向tail的后继节点 head->next = tail->next; // tail指向当前头节点，完成局部反转 tail->next = head; // 返回反转后的新头节点 return newHead; }

✅ 代码关键解析：

  • tail 保存了当前节点的直接后继，是回溯时调整指针的核心；
  • 递归会一直深入到待反转的最后一个节点，回溯时从后往前调整指针，完美实现反转；
  • 未反转的节点完全不影响，保证了链表的完整性。

🎯 实战攻坚：LeetCode 92 链表区间反转

1. 题目问题描述

LeetCode 92. 反转链表 II：

给你单链表的头指针 head 和两个整数 m、n（1 ≤ m ≤ n ≤ 链表长度），请你反转从位置 m 到位置 n 的链表节点，返回反转后的链表。

2. 神器加持：虚拟头节点（哨兵）技巧

这是链表题中解决边界问题的万能技巧！

  • 定义：创建一个额外的链表节点（值任意，如0），让它的next指向原链表的头节点，这个节点就是虚拟头节点（dummy）；
  • 核心作用：消除「待反转区间包含原链表头节点」的特殊情况，统一所有操作逻辑，类似哨兵节点的防护作用。

我们用Mermaid图直观展示虚拟头节点的结构：

next

移动m-1步

m=2

虚拟头节点 dummy\nval=0

节点1

节点2

节点3

null

指针p

指针p

📌 图表说明：虚拟头节点独立于原链表，指针p只需移动m-1步，就能精准定位到待反转区间的前驱节点，无论m=1还是m>1，逻辑完全一致。

3. 整体解题思路

将区间反转问题拆解为3个简单步骤，完美复用我们的reverseN函数：

  1. 定位前驱节点：通过虚拟头节点，移动指针找到第m-1个节点（记为p），它是待反转区间的前一个节点；
  2. 计算反转长度：待反转节点数 k = n - m + 1；
  3. 调用工具函数+拼接：调用reverseN反转p.next开头的k个节点，将p.next指向反转后的新头节点，完成拼接。

4. 完整代码实现（C++）与逐行解析

 // LeetCode92 区间反转主函数 ListNode* reverseBetween(ListNode* head, int m, int n) { // 1. 创建虚拟头节点，指向原链表头 ListNode* dummy = new ListNode(0); dummy->next = head; // 2. 定义指针p，初始指向虚拟头节点 ListNode* p = dummy; // 3. 移动m-1步，定位到待反转区间的前驱节点 for (int i = 0; i < m - 1; i++) { p = p->next; } // 4. 计算需要反转的节点个数 int k = n - m + 1; // 5. 调用reverseN，反转p.next开头的k个节点 p->next = reverseN(p->next, k); // 6. 返回虚拟头节点的next（最终链表头） return dummy->next; }

✅ 代码关键解析：

  • 虚拟头节点彻底规避了m=1时头节点变化的边界问题；
  • 仅通过一次循环定位前驱节点，时间复杂度极低；
  • 核心反转逻辑完全复用reverseN，代码复用性拉满。

5. 算法复杂度分析

  • 时间复杂度： O ( n ) O(n) O(n) ，仅遍历链表一次，递归操作也是线性的；
  • 空间复杂度： O ( n ) O(n) O(n) ，递归调用会占用栈空间（若改用迭代实现reverseN，空间可优化为 O ( 1 ) O(1) O(1) ）。

📚 算法原理深度剖析

1. 递归反转的核心原理

链表递归反转的本质是后序遍历：先递归深入到子问题的终止节点，再回溯调整指针。

对于reverseN，我们把「反转前n个节点」分解为「反转前n-1个节点」的子问题，直到n=1到达终点，再逐层回溯调整指针，最终完成整体反转。

2. 虚拟头节点的底层逻辑

普通链表操作中，头节点没有前驱，当反转区间包含头节点时，需要单独写判断逻辑。虚拟头节点为原链表增加了一个「公共前驱」，让所有节点的操作逻辑完全统一，代码更简洁、更健壮。

💡 算法学习核心建议

结合本题的学习，给大家分享算法刷题的核心方法论：

  1. 思维与代码双管齐下：学习算法分为学思路和写代码两个过程，缺一不可。先理解递归分解、区间拆解的思维逻辑，再动手敲代码，才能真正内化；
  2. 基础工具优先掌握：复杂算法题都是基础工具的组合，比如本题的reverseN就是核心工具，吃透基础，进阶题迎刃而解；
  3. 实操大于空想：不要只看题解，跟着思路逐行敲代码，调试指针操作，才能攻克链表的指针难点；
  4. 刻意练习边界情况：链表题的坑点都在边界（如m=1、n=链表长度），刻意针对边界测试，提升代码健壮性。

结语

LeetCode 92 区间反转，是链表递归反转的里程碑式题目。它教会我们：复杂问题拆解为基础子问题，用工具函数简化核心逻辑，用技巧规避边界问题。

从反转前n个节点，到区间反转，不仅是代码的进阶，更是递归思维的升华。希望大家通过本文，彻底吃透链表反转的核心，在算法刷题的路上稳步前行！💪

✅ 关键点回顾

  1. 核心工具：reverseN递归反转链表前n个节点；
  2. 万能技巧：虚拟头节点统一链表边界操作；
  3. 解题核心：区间反转 = 定位前驱 + 调用基础反转函数 + 拼接链表；
  4. 学习方法：思路先行，代码跟进，刻意练习！
链表进阶核心 | LeetCode 92 区间反转：吃透递归反转与哨兵技巧

Read more

[算法]——链表（三）

[算法]——链表（三）

目录 编辑 一、前言 二、正文 1.重排链表 1.1 题目解析 1.2 算法原理 1.3 具体代码 2.K个一组翻转链表 2.1 题目解析 2.2 算法原理 2.3 具体代码 三、结语 一、前言         本文将继续为大家带来链表的学习！！！ 二、正文 1.重排链表 1. 重排链表 - [力扣] 1.1 题目解析         本题要求要求我们对所给链表进行重排，那么观察题目所给示例，我们会发现所谓重排后的链表，就是先头结点，尾结点，然后头结点的下一个节点，

By Ne0inhk

LeetCode 11 - 盛最多水的容器

思路 容器面积由 宽度 和 短板高度 决定。最优解一定藏在不断收窄宽度的过程中。 1. 初始化：left 指针在数组头部，right 指针在尾部。这是最宽的可能。 2. 移动策略：比较 height[left] 和 height[right]。 * 面积受限于短板。若移动长板，宽度变小，高度不变（或变小），面积必然减小。 * 因此，必须移动短板对应的指针。这虽然牺牲了宽度，但给了我们寻找更高板子的机会，面积才有可能增大。 3. 迭代：循环此过程，持续更新最大面积，直到两指针相遇。 C++ 代码实现 classSolution{public:intmaxArea(vector<int>& height){int

By Ne0inhk
【数据结构指南】深入二叉树遍历

【数据结构指南】深入二叉树遍历

前言：         在前文中，我们探讨了完全二叉树和满二叉树的概念与性质，并基于完全二叉树实现了堆这一数据结构。然而，对于普通二叉树的认识仍有待深入，本文将系统性地介绍普通二叉树的遍历相关内容。                   一、前置说明          一般而言，对于一棵普通二叉树是通过链式结构定义，即每个节点包含三个部分：          1.数据域（data）：用于存储节点的值          2.左指针（left）：用于指向左子节点          3.右指针（right）：用于指向右子节点                  typedef int BTDataType;//此处将 （int）整形 作为节点存储的内容 typedef struct BinaryTree { BTDataType data; struct BinaryTree* left; struct BinaryTree* right; }BTNode;                  在学习二叉树的基本操作前，需先要先创建一棵二叉树，然后才能学习

By Ne0inhk
【数据结构】彻底搞懂二叉树：四种遍历逻辑、经典OJ题与递归性能全解析

【数据结构】彻底搞懂二叉树：四种遍历逻辑、经典OJ题与递归性能全解析

🏠 个人主页:EXtreme35 📚 个人专栏: 专栏名称专栏主题简述《C语言》C语言基础、语法解析与实战应用《数据结构》线性表、树、图等核心数据结构详解《题解思维》算法思路、解题技巧与高效编程实践 目录 * 二叉树全栈进阶指南：从内存布局到递归本质的深度复盘 * 一、二叉树的底层逻辑与核心概念 * 1.1 核心定义与特点 * 1.2 二叉树的五种基本形态 * 1.3 特殊二叉树 * 1.4 二叉树的五条性质 * 1.5 存储结构 * 二、遍历的递归之美 * 2.1 前序遍历 * 2.2 中序遍历 (In-order Traversal) * 2.3 后序遍历 (Post-order Traversal) * 2.

By Ne0inhk