牛客网的链表题十个里面有八个都是冲着指针操作去的。今天聊的这道“链表内指定区间反转”算是我见过的最能检验基本功的题目之一。表面上是让你把链表里某个区间的节点顺序调个头实际上考的是对虚拟头节点的理解、对断链时机的把控以及对边界条件的敏感度。我当年第一次刷这道题的时候吭哧吭哧写了一堆判断逻辑结果提交之后先是数组越界后是段错误最后勉强跑通还是靠着一堆if硬凑出来的。后来重新梳理思路才发现这题根本不需要那么复杂。这篇就把我从暴力解法到标准解法的踩坑过程、指针细节、边界条件全部拆开聊透看完你再去刷题思路会清晰很多。1. 题目到底在问什么先手动走一遍流程1.1 把题目翻译成人话题目给的链表是单链表每个节点只有一个next指针没有prev指针。要求是把从m到n的这一段区间的节点顺序反转区间外的节点保持原样最后返回新的头节点。举个例子链表是 1 - 2 - 3 - 4 - 5 - NULLm2n4操作完之后应该是 1 - 4 - 3 - 2 - 5 - NULL。注意题目说的是“反转”不是“排序”也不是“位移”区间外节点的相对位置绝对不能变。我第一次做这题时走了不少弯路因为当时对链表的理解还停留在“顺着节点一个个访问”的阶段。链表不同于数组数组反转区间只要知道下标就能原地交换链表呢你没法随机访问只能通过指针一步步找过去而且单链表只有next指针你把某个节点的next指向别处之后原本后面的节点如果没被提前记录下来就直接丢了。这个过程不亲手画图光靠脑子想容易出错。1.2 从“整链反转”到“区间反转”的过渡如果你刷过“反转链表”那道入门题就会知道整条反转的思路是pre初始化为NULLcur指向head每次把cur-next指向pre然后precurcurcur-next。这中间容易踩一个坑如果先把cur-next改掉那cur原本的下一个节点就找不到了。所以整链反转都会用一个next指针暂存cur的下一个节点。区间反转比整链反转多了一个约束只反转m到n这一段。这意味着三件事。第一你得先找到第m个节点以及它前面的那个节点。第二从头节点到第m个节点之间的那一截不能动。第三第n个节点之后的那一截也不能动。怎么做到“不动”呢最简单的理解就是让所有指针操作都只发生在区间内部区间外部的next指向关系不要碰。这里有个容易想当然的地方很多人以为区间反转可以先把区间拆出来反转完之后再拼回去。理论上确实可行实际操作却很蠢因为你得同时记住区间前后两个边界节点拼接的时候还得处理区间前空、区间后空等各种特殊情况。最典型的做法其实是“边遍历边反转”也就是遍历到第m个节点开始每经过一个节点就把它“摘下来”插到区间头部走n-m步之后自然就反转完毕。1.3 虚拟头节点为什么是必需品这是我刷了几道链表题之后才真正想明白的点很多链表题目头节点是个烫手山芋。因为头节点没有前驱你想在它前面插入节点或者以它为基准做操作总是要单独写if (m 1)这种判断。区间反转里如果m1说明区间从链表第一个节点就开始此时区间前的那个“pre”节点根本不存在不处理就会空指针。解决思路很简单在链表最前面额外加一个虚拟头节点dummydummy-next指向原链表的头节点。这样所有节点包括原头节点都有一致的前驱操作逻辑完全统一了。最后返回dummy-next就是新链表的头节点。这个手法在很多链表题里都能用建议直接形成条件反射看到涉及头节点变更的题目先加dummy。虚拟头节点本身不存有效数据它的存在纯粹是为了简化代码逻辑。代价是内存上多开了一个节点但对于面试和刷题场景完全值得。2. 核心思路拆解:为什么“一次遍历”就够了2.1 用“局部头插法”替代“断开再拼接”整链反转的思路是逐个把指针方向掉头区间反转如果沿用这个思路会有一个明显的问题区间内反转完之后区间前的节点和区间后的节点怎么重新连上比如区间内反转之后原来的第m个节点会跑到区间末尾原来的第n个节点会跑到区间开头。你得让区间前一个节点指向原来的第n个节点让原来的第m个节点指向区间后一个节点。多出两个边界连接容易出错。换个角度想如果我在遍历区间的时候每遇到一个新节点就把它移动到区间最前面那结果是不是一样的举个例子假设链表是1 - 2 - 3 - 4 - 5区间是[2,4]。pre指向1cur指向2。第一次把cur的下一个节点也就是3摘下来插到pre后面链表变成1 - 3 - 2 - 4 - 5。第二次把cur的下一个节点也就是4摘下来插到pre后面链表变成1 - 4 - 3 - 2 - 5。两次操作结束后区间就已经反转了。这个过程的本质是“头插法”——每次把新节点插入到pre和cur之间经过n-m次插入之后区间内节点的顺序就反过来。这种写法优于“断开再拼接”的原因在于你不需要额外处理边界连接区间外的节点从头到尾都没动过。只要pre、cur指针的位置正确循环n-m次就自动得到答案。而且从逻辑上更符合“链表操作”的直觉——接接拆拆都在指针层面完成不依赖数组下标的思维。2.2 指针怎么定pre、cur、next三兄弟的分工我把区间反转拆成三个角色pre永远指向区间第一个节点的前一个节点也就是区间前驱cur永远指向当前未处理节点的前一个节点说白了就是区间操作开始时的第m个节点next是每一步的临时变量保存cur的下一个节点防止摘节点时丢失链表。第一次刷的时候我很容易搞混cur和pre的位置关系画了几张图才理清楚。关键点在于整个循环过程中pre不移动cur也不移动移动的只有next被不断更新。每次循环做四件事next cur-next保存下一个cur-next next-next把next从链中断开next-next pre-next把next插到pre后面pre-next next让pre的下一个指向next。这里最反直觉的地方在第三步和第四步为什么next要先指向pre-next而不是直接指向cur因为pre-next在第一次循环之后可能已经不是cur了。第一次循环时pre-next确实是cur但经过一轮头插之后cur的位置已经变了。如果直接next-next cur那插进去的顺序就是反的。必须让新节点始终插在pre和“当前区间最新头节点”之间才能真正做到反转。再强调一遍循环次数是n-m不是n。因为只需要把区间内后面的每个节点依次搬到前面去搬n-m次就完成了。如果写成循环n次或者循环到cur-next NULL都会把区间外的节点也卷进来逻辑就乱了。2.3 空间复杂度为什么只有O(1)这题的标准解法只用到了常数个额外指针变量不管链表多长额外空间占用都不变。对比一下用数组存节点再倒序重建的解法虽然也能过但空间复杂度是O(n)代码写起来倒是简单面试官问一句“能不能优化空间”你就不好回答了。为什么强调空间复杂度因为链表题核心就是考察指针操作能力你如果每次都把节点取出来放数组里排序那和做数组题有什么区别真正的链表高手追求的是一遍遍历、O(1)空间、常数级额外指针就把问题解决。这不是炫技而是实际工程中链表节点可能是大对象比如复杂的结构体拷贝和缓存的开销远高于直接用指针操作。我刷题时的习惯是每道题都先想一想“能不能原地改指针完成”想不出来再看题解。区间反转这道题原地写法并不难关键是理解了头插法之后代码量控制在二十行以内是完全没问题的。3. 完整代码实现:C语言版、C版、Java版对照3.1 C语言实现把每一步写到注释里我用的是C语言风格的结构体题目要求的是单链表定义大概是struct ListNode { int val; struct ListNode *next; };核心函数实现struct ListNode* reverseBetween(struct ListNode* head, int m, int n) { // 处理特殊情况空链表或只有一个节点或区间长度为1 if (head NULL || head-next NULL || m n) { return head; } // 创建虚拟头节点统一边界处理 struct ListNode dummy; dummy.next head; // pre定位到区间前一个节点 struct ListNode *pre dummy; for (int i 1; i m; i) { pre pre-next; } // cur指向区间的第一个节点 struct ListNode *cur pre-next; // 循环 n-m 次依次把后面的节点头插到pre后面 for (int i 0; i n - m; i) { struct ListNode *next cur-next; cur-next next-next; next-next pre-next; pre-next next; } return dummy.next; }有几点说明。第一虚拟头节点我直接用了局部变量没有malloc因为它的生命周期只在函数内部不需要动态分配也省去了free的麻烦。第二种定位pre的时候循环条件是im注意m是从1开始计数的所以要循环m-1次。比如m2pre该指向第1个节点循环1次即可。第三核心循环in-m循环次数严格等于区间内移动次数。这段代码里最容易漏的就是mn的判断。如果不加循环次数为0返回结果也是对的但会导致一些不必要的指针操作万一遇到区间长度为0的场景可能越界。养成提前处理边界的好习惯。3.2 C版本写法几乎一样C版唯一区别在于结构体的定义和内存管理。如果你用的是C结构体可以写得更简洁也可以直接用nullptr替代NULLstruct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { if (head nullptr || head-next nullptr || m n) { return head; } ListNode dummy(0); dummy.next head; ListNode *pre dummy; for (int i 1; i m; i) { pre pre-next; } ListNode *cur pre-next; for (int i 0; i n - m; i) { ListNode *next cur-next; cur-next next-next; next-next pre-next; pre-next next; } return dummy.next; } };C里如果用了new创建节点记得在测试代码里delete清理不过算法题通常只要求实现函数体不需要处理内存释放。3.3 Java版本引用类型的天然适配Java没有指针概念但引用变量本质上就是指针写法逻辑完全一致public ListNode reverseBetween(ListNode head, int m, int n) { if (head null || head.next null || m n) { return head; } ListNode dummy new ListNode(0); dummy.next head; ListNode pre dummy; for (int i 1; i m; i) { pre pre.next; } ListNode cur pre.next; for (int i 0; i n - m; i) { ListNode next cur.next; cur.next next.next; next.next pre.next; pre.next next; } return dummy.next; }Java里对空指针尤其敏感好在这题所有操作都建立在cur和next不为null的前提下。只要m、n合法cur永远有值next也一定有值因为循环次数只到n-m而n位置的节点一定存在。4. 手动画图推算全过程从指针角度验证每一步4.1 选定一条具体链表逐行执行纸上得来终觉浅链表题必须亲手推演。我们拿一个具体例子走一遍完整流程。链表1 - 2 - 3 - 4 - 5 - NULL 参数m2n4 预期结果1 - 4 - 3 - 2 - 5 - NULL第一步创建dummy节点dummy.next head。所以现在是dummy - 1 - 2 - 3 - 4 - 5pre dummy。第二步循环i从1到m-1也就是i1时pre pre-next。此时pre指向节点1。cur pre-next所以cur指向节点2。现在的关键指针状态pre - 节点1cur - 节点2第三步进入主循环i0。next cur-next所以next指向节点3。 cur-next next-next把节点2的next指向节点4链表暂时变成1 - 2 - 4 - 53暂时脱离链表next-next pre-next节点3的next指向pre-next。记住此时pre-next还是节点2所以节点3指向节点2。pre-next next节点1的next指向节点3。完成第一次循环后链表变成1 - 3 - 2 - 4 - 5对比一下原来的链表节点3被提到了节点2前面但注意这里的核心变化cur仍然指向节点2pre仍然指向节点1。节点2的next已经从3变成了4。所以从整体上看节点顺序是1、3、2、4、5。第四步主循环i1。next cur-next。cur还是节点2cur-next此时是4所以next指向节点4。 cur-next next-next节点2的next指向节点5。 next-next pre-next节点4的next指向pre-next。此刻pre-next是节点3所以节点4指向3。 pre-next next节点1的next指向4。完成第二次循环后1 - 4 - 3 - 2 - 5完美这就是我们预期的结果。整个过程中cur一直没动始终是原区间的第一个节点。每次循环就是把它后面的节点摘下来插到pre后面。循环结束区间内部的顺序就自然反转了。4.2 如果m1会发生什么现在试试m1n3的场景链表还是1 - 2 - 3 - 4 - 5。按代码走一遍pre定位时循环一次都不会执行pre还是指向dummy。cur pre-next也就是原头节点1。进入主循环第一步操作next 2 cur-next 2的next也就是3所以1连接到3 2的next pre-next 1pre-next当前是1 pre-next 2链表变成dummy - 2 - 1 - 3 - 4 - 5第二次循环next cur-next 3 cur-next 3的next 4 3的next pre-next 2 pre-next 3链表变成dummy - 3 - 2 - 1 - 4 - 5最后返回dummy.next就是节点3。完美反转了前三个节点。如果没有dummy节点m1时pre就不知道该指向谁了。这也是我强烈推荐虚拟头节点的原因它让边界情况彻底消失。4.3 如果n等于链表长度区间延伸到末尾这种情况也无需额外处理。比如链表1 - 2 - 3 - 4m2n4。执行逻辑第一次循环后1 - 3 - 2 - 4 第二次循环后1 - 4 - 3 - 2循环结束时cur指向节点2它后面已经是NULL了不影响。返回1 - 4 - 3 - 2完全正确。区间延伸到末尾时只要循环次数写对就不会出现访问空指针的问题。5. 常见错误与边界问题这些坑我都踩过5.1 没保存next就直接改指针导致链表断链这是最典型错误。很多新手写链表题一上来就让cur-next pre然后发现自己找不到后面的节点了。区间反转里也一样如果你在循环体里严格执行“先保存next再移动指针”基本不会出错。我见过不少同学把顺序写颠倒先改了pre-next再取next结果next指向的根本不是原来的后续节点链表直接就乱了。实操建议在循环体的第一行就写好next cur-next这种防御性写法看着不优雅却能省下无穷无尽的调试时间。还有如果感觉乱用笔纸画图把循环体每一步四个操作对照着画一遍基本就不会写错了。5.2 虚拟头节点申请了却忘记释放在C语言中如果你用malloc创建dummy最后需要free但要注意不能把新头节点也free掉。我的做法是能不用动态内存就不用直接在栈上定义一个struct ListNode dummy。在C里也可以直接用构造函数创建栈对象。只有Java和Python这些自带GC的语言不用考虑这个问题。面试时如果现场写代码用栈上的虚拟头节点还有一个好处不需要写free减少代码噪音也让面试官更关注你的算法逻辑本身。5.3 循环次数写成n而不是n-m这是区间反转最容易写错的地方。一开始我没有仔细思考想当然写了for(int i m; i n; i)结果每个节点都被处理了链表被翻来覆去改了好几遍输出完全错误。正确写法是循环执行n-m次因为区间内除了第一个节点其余n-m个节点都要被“搬到前面去”。理解这一点之后你就不会数错了。再换一种理解方式区间长度是n-m1第一个节点不需要移动真正需要移动的是后面的n-m个节点。每次移动一个节点正好n-m次。5.4 m和n合法性的假设题目一般约定1 ≤ m ≤ n ≤ 链表长度所以不需要额外判断。但实际项目中如果有类似的链表操作函数一定要加上合法性检查否则传入m0或n超过长度代码里会出现空指针解引用。刷题归刷题工程习惯不能丢。5.5 反转后“头节点”可能变了你要会返回新头如果m1反转完原头节点已经被移到了区间末尾新头节点是原第n个节点。如果没有dummy返回head就会出错。使用dummy后统一返回dummy.next无论头节点怎么变都能正确返回。这个细节在链表题中属于基本功背下来也不为过。6. 进阶思考这题背后的通用方法论6.1 区间反转是很多复杂链表题的基础组件倒过来想如果让你反转链表中第k个节点到末尾也就是“K个一组翻转链表”的雏形区间反转就是特例。如果再引申一下把区间反转当成一个子函数你就能写出K个一组翻转的循环解法每次找到一段长度为K的区间调用区间反转然后移动pre到新的位置。很多看起来很难的链表题拆解开就是若干个“区间反转”的组合。所以我的建议是把这题吃透不仅是为了通过牛客的测试用例更是为了后续储备。在面试中遇到“每K个节点一组反转”或者“从链表尾部开始计数反转”的变形题你有区间反转这个组件思路会顺很多。6.2 链表题画图比看十遍代码有效很多人刷题有一个误区盯着代码看试图在脑子里模拟指针变化。我发现最高效的方式永远是动手画。画一个小链表把每个节点用一个方框表示next指向用箭头表示每次指针修改就重画一遍箭头。画到第三次循环的时候你自然就理解了每一步操作的意义。不要嫌麻烦链表题本质是空间想象题和初中几何一样光看不动笔很难真正掌握。6.3 复杂度分析不能丢时间O(n)、空间O(1)这个解法的时间复杂度是O(n)因为两个循环加起来遍历了一次链表没有嵌套遍历。空间复杂度O(1)只用常数个指针变量。面试时如果被问复杂度就照这个答。要是有人给你一个用递归的版本也可以写但递归在链表很长时容易爆栈非递归写法更稳妥。7. 牛客平台使用体验与调试技巧7.1 牛客的判题环境、输入输出格式牛客的链表题通常不需要你处理main函数和输入输出它给出的是类的接口或者函数声明让你填空。以C为例题目会给出ListNode结构体定义和一个Solution类你只需要把函数体补全。所以平时练习时可以在本地写一个简单的main函数自己构造链表、调用函数、打印结果上线提交时再只保留核心函数。本地验证方法很简单写一个辅助函数void printList(struct ListNode *head) { while (head ! NULL) { printf(%d , head-val); head head-next; } printf(\n); }再写一个创建链表的辅助函数手动构造几个节点调用你的reverseBetween之后打印结果和预期对比。如果不一样用gdb或调试器打断点也可以直接在纸上模拟。7.2 牛客提交时的常见报错类型第一是编译错误通常是结构体定义写错或者漏了头文件。牛客的环境一般自带头文件但如果你使用malloc需要包含stdlib.h本地编译器会提示线上可能不会。第二是段错误。出现段错误绝大多数情况下是空指针或者野指针检查一下m、n是否合法检查cur-next是否为NULL。第三是输出格式错误牛客会校验输出格式不过链表题一般不要求你写输出函数这点反而省心。第四是运行超时。区间反转的时间复杂度是O(n)不太可能超时。如果超时多半是在代码里写了死循环比如循环条件用n而不是n-m或者移动pre时没有前进导致永远定位不到正确位置。7.3 遇到“返回值不对但又不报错”时怎么排查这种最头疼能编译能运行就是结果错误。我的排查步骤是先在草稿纸上对着小数据集长度5、区间[2,4]逐步模拟看结果和预期在哪一步分岔如果模拟不出来在本地代码中把每个循环结束后的链表打印出来对比中间状态。区间反转的中间状态应该每循环一次就多一个节点被正确插入到pre后面如果某一次循环前后链表顺序没变多半是那一轮指针操作顺序写错了。注意一个细节打印中间状态时要从dummy.next开始不能从head开始因为head可能已经被移走了。8. 从这道题延伸出去链表的其他高频考法8.1 链表反转的几种变体都是“兄弟题”面试中链表反转类题目的出场率极高常见版本有整链反转、区间反转、K个一组反转、链表反转从第m个节点到末尾、两两交换相邻节点。做熟区间反转之后两两交换其实就是区间长度为2的反转每两次操作交换一对节点K个一组反转就是反复调用区间反转的变体。这些题目在代码上高度相似只是循环条件不同。建议刷题时把它们放在一起对比着做整理一张“反转家族”对照表比如区间长度、是否需要dummy、循环次数分别是多少。这种横向对比比孤立刷题更高效。8.2 链表遍历的底层思维永远要有“三步走”意识所谓三步走就是修改next指向时先保存后路再改指向最后移动指针。每一个在链表上动指针的操作都可以拆成这三步。我见过很多代码写得飞快的人遇到复杂链表题依然会翻车原因就是没有形成这种条件反射。在区间反转里三步走的每一步都体现在那四行循环体代码里。掌握之后你写任何链表操作都会顺手很多。8.3 善用牛客讨论区的题解但务必独立思考后再看牛客题库的每道题都有讨论区里面有很多人的题解和踩坑记录。我刷题时的习惯是先自己硬想半小时想不出来再看题解。直接看题解的缺点是你以为自己懂了第二天又不会了。真正有效的方法是看完题解后合上屏幕自己默写一遍代码然后跑测试用例。能够独立默写出来说明这道题你基本掌握了。如果默写到一半卡住说明那个地方还没理解透再回去看这样记忆最牢固。最后再分享一个个人小习惯我把这道题的解题模板抄在了笔记里单独列了一页“链表反转万能模板”包括dummy节点的创建、pre的定位、n-m次循环、四行核心指针操作。后来做K个一组反转、反转链表II都直接套这个模板改改参数。模板不是用来背的而是在理解了原理之后把它收进自己的工具箱遇到类似需求时能快速反应。链表这种东西说到底就是“画图动作分解”只要心不慌一个个节点理清楚没有解决不了的问题。