★ FEATURED ARTICLE 链表面试八股年年有链表反转永远是那道绕不开的开门题。我帮别人改过不少代码也自己踩过坑发现大部分人不是不会写而是没弄明白“反转”这个动作到底对节点做了什么。这篇就从头捋一遍链表反转从最基础的迭代法到递归、区间反转、K个一组反转再到双向链表把每一步为什么这么做讲清楚顺便把调试时容易翻车的地方一并列出来。无论你是刚接触数据结构的初学者还是准备笔试面试前想快速过一遍这篇都适用。1. 先弄懂链表反转到底在“反转”什么1.1 链表这个数据结构是怎么回事链表和数组最大的区别在于数组在内存里是一块连续的区域一个人挨着一个人站好你只要知道第0个的位置后面的人都能按序号找到。链表则更像一队人手拉着手每个人只记得下一个人是谁前面的人不拉着后面的人后面的人就丢了。单链表的每个节点一般就两块内容一块存数据一块存指向下一个节点的指针通常命名为next。一个典型的节点定义长这样我用最常见的单链表来举例struct ListNode { int val; struct ListNode *next; };创建链表的时候我们会用一个head指针指向第一个节点也就是队伍的排头。只要head不丢整条链就都能通过next一个一个摸下去。这也意味着链表天然不适合随机访问你想找第3个节点没办法直接下标索引只能从头开始走两步。但链表的好处也很直接在中间插入和删除节点非常快只要改相邻节点的指针即可不像数组需要挪动大片元素。很多人一开始学链表会觉得抽象其实你就把它想成寻宝游戏每张纸条上写着宝藏的位置和下一张纸条在哪里你永远只能根据当前纸条找下一张。理解了这一点链表反转的所谓“难”本质上就只是纸条上的“指向”要被全部改一遍。1.2 反转的“反转”到底反转了什么先说结论链表反转不是把数据val倒过来存而是把每个节点里next指针的方向反过来同时把head移到原来链表的尾节点上。比如原来是这样的1 - 2 - 3 - 4 - 5反转之后应该是5 - 4 - 3 - 2 - 1你仔细观察节点本身没有变1还是那个15还是那个5变的是连接关系。原本1指向2现在1要变成指向NULL原本2指向3现在2要指向1原本5指向NULL现在5要指向4并且5成为新的head。这个“指向反转”看起来简单动手写的时候特别容易栽跟头。最常见的错误就是你正想把当前节点的next指向前一个节点结果发现原来的下一个节点找不到了因为next已经被覆盖了。所以解法才需要第三个指针提前把后面的节点保存下来。这也是“三指针迭代法”存在的根本原因不是说三根指针花里胡哨是如果不先存一下链表就断在你手里了。理解到这一层后面所有反转方法都能看成对同一个问题的不同回答如何在保存后继、修改当前指向、移动前驱这三件事之间寻找一个安全的顺序。2. 迭代法三根指针走天下2.1 为什么要用三根指针迭代法是最直白的解法思路只有四个字边走边改。你从head出发每走到一个节点就把它指向前一个节点。可是它原本指向后一个节点改了之后后一个就找不到了怎么办那就用一个临时指针在修改之前先把后一个节点记下来。所以我们需要三个角色prev当前节点的前一个节点初始化为NULL。为什么是NULL因为反转后原来的头节点要变成尾节点尾节点的next必须是NULL。cur当前正在处理的节点初始化为head。next保存cur原本的后继节点防止cur的next被覆盖后找不到路。用比喻来说prev是已经倒好方向的人cur是正在掉头的人next是排在你后面还没轮到的人。你不能在cur掉头的时候把next的手松开松开了整支队伍后半截就散伙了。2.2 逐行拆解迭代反转的循环体这里我直接给出简洁版本用最基础的语言写方便你看到代码时能对应上刚才说的逻辑struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev NULL; struct ListNode *cur head; while (cur ! NULL) { struct ListNode *next cur-next; // 先保存后继 cur-next prev; // 指针反向 prev cur; // prev前进 cur next; // cur前进 } return prev; }一行一行拆开看。进入循环时cur指向当前节点第一行先把cur的后继存进next。为什么要先存因为下一行cur-next prev会直接把cur指向后面的线切断如果不提前保存循环后面cur next这一步就不知道该往哪儿走了。第二行是真正的“反转动作”把当前节点的next从后面改成前面。第三行和第四行是滑动窗口prev走到cur的位置cur走到刚才保存的next位置。整个过程就像一条履带往前滚动每滚过一个节点这个节点的箭头就掉了个头。循环结束的条件是cur NULL说明已经走完了整个链表最原始的头节点也处理完了。此时prev指向的是原链表的最后一个节点也就是反转后链表的第一个节点所以直接return prev。这一步很多初学者会漏写成return head结果反转后头节点还是旧的遍历出的链表只剩一个节点或者干脆成环。2.3 迭代实现的边界条件边界条件无非就是三种空链表、只有一个节点、正常多节点链表。空链表head是NULLwhile循环一开始就不满足直接return prev也就是NULL这个行为是合理的空链表反转后还是空链表。单节点链表head不是NULL进入循环一轮next是NULLcur-next变成prev也就是NULL然后prev变成curcur变成NULL循环结束返回prev也就是原来的唯一节点。所以这两种情况不需要额外写if判断迭代法天然兼容。但面试中常被追问的一个点在于这个解法的时间复杂度和空间复杂度。时间复杂度显然是O(n)因为每个节点只访问一次。空间复杂度是O(1)因为我们只用了固定数量的临时指针没有额外开数组或递归栈。很多人写递归被追问空间复杂度时答不上来其实是不知道递归的空间开销来源这个我放到下一节讲。我自己的经验是迭代法写熟之后连带着对指针操作的理解都会上一个台阶不再怕“改了一个指针导致丢一串”这种问题。建议新手第一阶段就练这个写法练到可以闭着眼睛在纸上画出来。3. 递归法先走到链表尽头再回头3.1 递归是哪一步“递”哪一步“归”迭代法是“从头开始边走边改”递归法则完全反过来是“先走到头再回头改”。很多人第一次看递归反转的代码会觉得像魔法尤其是那行head-next-next head怎么看都不太对劲。我建议你别背代码先理解递归的“递”和“归”两个过程。“递”的阶段就是一直调用自己传入head-next一层层往下钻直到head为NULL或者head-next为NULL才停。为什么停在这个位置因为链表只有0个节点或1个节点时它反转后还是自己不需要再操作了这是递归的终止条件。“归”的阶段就是从最后一个节点开始一层层往上返回每返回一层就把当前层的节点接到已反转部分的下一个位置。这时候真正的指针修改全都发生在“归”的过程中而不是在“递”的过程中。3.2 经典递归写法逐层拆解直接看标准写法struct ListNode* reverseList(struct ListNode* head) { if (head NULL || head-next NULL) { return head; } struct ListNode *newHead reverseList(head-next); head-next-next head; head-next NULL; return newHead; }我们用链表1 - 2 - 3来推演。调用reverseList(1)发现1-next不是NULL于是调用reverseList(2)reverseList(2)又调用reverseList(3)到3这里3-next是NULL直接返回3。所以reverseList(2)拿到的newHead是3此时链表是1 - 2 - 33已经是被“反转后”的新头。接着执行head-next-next head对于reverseList(2)这一层head是2head-next是3所以这句话等价于3-next 2把3指向2。然后head-next NULL即2-next NULL。这一步看起来把2和原本3的连接断开了但前面刚把3指向2所以此时局部链表变成了3 - 2而1仍然指向2。返回newHead也就是3给上一层。再回到reverseList(1)这一层head是1head-next还是2执行1-next-next head等价于2-next 1再把2指向1。然后1-next NULL。此时3 - 2 - 1整条链反转完成。关键点在于每一层递归返回时head-next这个节点已经是新链表的尾节点所以把head接在它后面再把head自己的next置空就保证了局部不会乱。很多初学者拿到这段代码最困惑的地方是为什么每次都要head-next NULL如果不置空链表尾部就会指向一个不该指向的节点甚至可能形成环。置空这一步在每一层递归里都执行最终只有最开始的head被置成NULL刚好作为反转后链表的尾部。3.3 递归的栈开销与适用场景递归写法代码极短思路也很优雅但它有一个隐藏成本每次递归调用都会在系统调用栈上压入一层栈帧保存当前的参数、返回地址等信息。链表如果很长递归深度就跟链表长度一样大。这个开销是O(n)的额外空间而迭代法只需要O(1)。在纯粹追求空间效率的工程环境里递归不一定是最好的选择。不过面试中递归写法仍然很有价值它考察的是你能否把一个复杂问题拆分成结构相同的子问题能不能理解函数调用栈的展开与回收。很多人只背代码不理解一旦面试官问“递归反转的时间空间复杂度各是多少”就会卡住。你可以这么记时间一定是O(n)因为每个节点都处理了一遍空间不是O(1)是O(n)这n不是数据占的空间而是递归栈深度的代价。实际操作中如果链表长度在几千这个量级递归完全没有问题但如果生产环境里可能出现几十万甚至更长的链表就要谨慎。递归深度过大可能撑爆调用栈导致程序崩溃。有些语言还能开启尾递归优化但链表反转这种操作本身也不是尾递归形式所以不能指望编译器帮你优化栈深度。4. 从“整条反转”到“局部反转”区间反转与K个一组反转4.1 反转m到n之间的节点整条链表反转是基础但实际面试里更常碰到的是局部反转。最典型的题目是给你单链表头节点以及两个整数m和n要求只反转从位置m到位置n之间的节点其他部分保持原样。比如链表是1 - 2 - 3 - 4 - 5m2n4反转后应该是1 - 4 - 3 - 2 - 5。1和5都不动中间三个节点顺序颠倒了。这个题的做法可以复用迭代法的三指针思路只是多了两个定位步骤。先让一个指针从head出发走m-1步停在要反转区间的前一个节点上记为pre。这个pre是区间左边界前面的节点它最后要指向反转后的区间头。区间起点就是pre-next记为cur。接下来要做的事情是把cur后面的节点一个一个搬到pre的后面相当于反复做“头插法”。这里我贴一个我们用头插法实现区间反转的示例代码如果你用的语言是Java或Python逻辑完全相同只是语法不同struct ListNode* reverseBetween(struct ListNode* head, int m, int n) { struct ListNode *dummy malloc(sizeof(struct ListNode)); dummy-next head; struct ListNode *pre dummy; for (int i 0; i m - 1; i) { pre pre-next; } struct ListNode *cur pre-next; for (int i 0; i n - m; i) { struct ListNode *moved cur-next; cur-next moved-next; moved-next pre-next; pre-next moved; } return dummy-next; }先解释dummy这个哨兵节点。为什么要它因为如果m1区间反转的头节点就是整个链表的头节点那pre就是NULL所有基于pre-next的操作都会崩。dummy是一个临时头节点它的next指向head这样即使m1pre也能被定位到dummy这个节点上操作起来一视同仁。最后返回dummy-next而不是dummy本身因为dummy是我们自己造出来的不应该出现在结果链表中。内层循环的每一步moved都是cur的下一个节点。第一次循环cur是2moved是3把cur-next指向4也就是moved-next3被“摘”出来然后把3的next指向pre-next此时是2再把pre-next改成3。一次操作后链表变成1 - 3 - 2 - 4 - 5。第二次循环cur还是2moved变成4再把4摘出放到pre后面变成1 - 4 - 3 - 2 - 5。循环次数是n-m次也就是区间长度减一正好把所有区间的节点搬到pre后面此时区间内顺序自然就反过来了。这个写法的好处是每轮操作都只需要O(1)时间总共O(n)次循环不需要把区间单独拆出来再拼接不容易漏接边界。4.2 K个一组反转的哨兵节点用法如果说区间反转还能硬推出来那“每K个节点一组反转不足K个保持原样”这类题目就更烧脑。题目要求通常是给定链表每K个节点反转一次最后一组如果长度不足K则不反转。比如1 - 2 - 3 - 4 - 5K2结果是2 - 1 - 4 - 3 - 5。这种题目的核心可以拆成两步第一步判断剩余节点够不够K个第二步对当前这K个节点做反转然后把前后接好。第二步本质上就是复用区间反转的“头插法”只不过区间长度固定为K。先给一种我认为最容易理解的迭代实现思路创建一个dummy哨兵节点dummy-next head。用prePrev指向每一组前面的节点初始为dummy。计算出链表总长度len然后每次循环判断len剩余是否不少于K如果少于K就直接结束。在每一组内用类似区间反转的循环把区间内第2个到第K个节点依次头插到区间头部之前。循环次数是K-1次。处理完一组后让prePrev跳到这一组反转后的最后一个节点同时len减去K。很多实现里会先统计链表长度因为这样就能提前知道最后一组还够不够K个不满足就直接跳出。也有另一种做法是每轮先用一个临时指针走K步探测走不满K步就说明已经到末尾停止处理这样就不需要先统计总长度。两种我都试过先统计总长度的好处是逻辑更直接代码读起来不容易晕代价是多花一遍O(n)遍历链表探测法的好处是只扫一遍但循环边界容易写错尤其是指针为空时的处理。实际笔试题里更推荐用先统计长度的方法哪怕多一次遍历也让代码稳定很多。面试官如果追问能不能优化到一遍你再告诉他可以用快慢探测处理最后一组展示自己确实理解差别所在。这里不做完整代码铺开重点提醒两个特别容易踩的坑每组反转后prePrev应该移动到哪很多同学还在原地下一组开始位置就错了。最后一组不足K个时不能反转但前面已经反转过的组的尾巴要接对不能把最后一组的头节点弄丢。我在辅导A同学写这道题时他连续两次都在“prePrev跳转到新组的尾节点”这一步出错原因是他误以为prePrev是反转前那一组的头节点。记住一个原则每处理完一组prePrev要指向这一组在新链表中的最后一个节点也就是下一组前驱的那个位置。我后来让他每轮开始前先把prev的最终值画在纸上再写代码一下就顺了。5. 双向链表反转别被多出来的一根指针绕晕5.1 双向链表反转的指针交换双向链表和单链表最大的不同是每个节点除了指向后继的next还有一个指向前驱的prev。看起来反转时要做的事情变多了但实际上复杂度并没有本质上升只是你需要在循环里同时处理两根指针的交换。双向链表节点定义通常是这样struct DoubleListNode { int val; struct DoubleListNode *prev; struct DoubleListNode *next; };反转的思路仍然是遍历链表对每个节点交换它的prev和next。这里有个容易犯傻的地方如果你把当前节点的next赋给prev之后接着想用原来的next继续遍历就要提前保存。很多新手直接写“交换”两个指针结果发现走到一半回头了死循环出不去。正确的迭代写法是这样struct DoubleListNode* reverseDoubleList(struct DoubleListNode* head) { struct DoubleListNode *cur head; struct DoubleListNode *tmp NULL; while (cur ! NULL) { tmp cur-next; // 先保存原来的后继 cur-next cur-prev; // 反转方向 cur-prev tmp; // 前驱变成原来的后继 cur tmp; // 继续移动 } return head; // 不对应该返回新的头 }等一下这个写法最后返回head是不对的。你想想遍历完整个链表后cur已经变成NULLhead还是原来的头节点而原来的头节点这时候已经是尾节点了。反转后真正的头节点是原来的尾节点所以需要在循环里记录最后一次交换时cur的位置或者更简单一点循环结束后最后一个非NULL的节点就是新头可以用一个变量始终保存“上一次访问的节点”最后返回它。这里我直接给修正逻辑struct DoubleListNode* reverseDoubleList(struct DoubleListNode* head) { struct DoubleListNode *cur head; struct DoubleListNode *prev NULL; while (cur ! NULL) { prev cur; struct DoubleListNode *next cur-next; cur-next cur-prev; cur-prev next; cur next; } return prev; }每次进入循环先把当前节点记录到prev里然后保存next再交换两根指针最后cur走向next。循环结束后prev就是最后一个处理过的节点也就是原链表尾节点它现在没有后继没有前驱但实际上它应该作为新链表的头。返回prev就对了。如果节点头尾带哨兵呢有些工程实现里双向链表会有一个固定的head哨兵节点不存实际数据仅用于标记链表的开始。反转带哨兵的双向链表本质上就是把头尾哨兵的next和prev互相换一下中间普通节点的交换逻辑不变。这个场景在工程里遇到不多但理解了不带哨兵的正反逻辑后再去套也容易上手。说到底双向链表反转只比单链表多了一行指针操作但真正难的是“交换之后如何继续遍历”这个点。我自己第一次写的时候也忘了先保存next导致死循环后来总结出一个习惯凡是涉及一个节点同时改动next和prev的操作第一步永远是先把原next保存下来否则任何“交换”都是空中楼阁。6. 调试技巧与常见错误排查实录6.1 纸上推演与日志打印链表题最讨厌的地方在于它不像数组题可以直接打印下标看内容链表一旦指针乱了你打印整个链表的时候可能直接死循环因为某个节点的next指回了自己程序永远走不到NULL。所以我调试链表反转从来不会直接只打印节点数据而是先检查“是不是成环了”。我的调试习惯是这三步第一步先写一个打印链表的工具函数。打印时用一个计数器限制最大打印个数比如超过100个节点就强制停止并提示“疑似成环”防止程序卡死。void printList(struct ListNode* head) { struct ListNode *cur head; int count 0; while (cur ! NULL count 100) { printf(%d - , cur-val); cur cur-next; count; } if (cur ! NULL) { printf(... (possible cycle, stopped)\n); } else { printf(NULL\n); } }第二步在反转函数里每次循环结束可以打印prev、cur的值甚至打印当前局部链表。不过更推荐的做法是对链表长度比较小的情况直接在纸上画出每个节点和指针的变化。我教别人写链表时经常让他们画这样的表一行是pre、cur、next当前分别指向哪个节点走一步填一行。画完三轮循环代码里再出错就说不过去了。第三步如果还查不出问题就去验证返回值。很多人迭代法写完后返回prev是错的因为prev在循环结束时确实指向新头但如果你在循环内用了额外的变量可能你在别处把prev意外改掉了。验证返回值时写一个断言反转后的链表头节点的val必须等于反转前尾节点的val。6.2 高频Bug速查表我发现很多问题翻来覆去就那几个这里整理一个速查表你遇到对应症状可以直接对照排查。症状可能原因修复思路反转后链表只剩一个节点循环体里没有正确移动cur或者return了head检查循环最后有没有cur next返回值必须是prev程序死循环打印链表停不下来某些节点的next没有被重定向到NULL或者形成了环检查每轮递归/迭代中的尾部置空操作用限制次数打印发现环区间反转后原链表前半部分丢了pre定位错误或者dummy使用不对确认pre要从dummy出发而不是从head出发m1时尤其注意K个一组反转后拼接错乱每组反转后前驱没有移动到新组的尾节点每处理完一组要把前驱更新为新组最后一个节点递归反转后返回的是旧head递归没有返回newHead而是返回head所有非终止条件都要return newHead双向链表反转一半卡住没有先保存next就交换了prev和next先保存原后继再交换指针最后移动curhead为NULL时崩溃没有判空入口迭代法天然兼容空链表递归法也要加head NULL还有一种很隐蔽的错误是在区间反转时循环次数写错。比如反转位置m到n一共涉及n-m1个节点如果循环写成了n-m1次头插结果会多搬一个节点局部结构错乱。这个最好通过纸上推演一次2到4的区间来校验。6.3 我自己的复盘建议链表反转这题很多人刷过一遍觉得会了过两周再写又卡壳。我的建议是别贪多就抓两个核心一是“保存后继”的思路二是“画表推演”的习惯。只要能熟练画出三指针迭代过程递归写法你再去理解就不难因为它只是把迭代的“前进”换成了函数调用栈的“回归”。如果你正在准备面试我建议这三种写法至少每种都亲手写到能一次通过迭代版、递归版、区间反转版。写的时候不要开编译器提示直接在白纸上写写完再对着测试用例过一遍。因为面试现场通常只有白板和编辑器没那么多机会让你试错。K个一组反转按需掌握如果你面的是算法岗或基础架构方向这题出现频率不低如果是业务开发方向迭代和递归基本够用。最后再分享一个小技巧链表题出错时不要急着改代码先把你每一轮循环中prev和cur的值写出来跟正确的推演结果比对。往往第一个不一致的地方就是代码里的问题所在。这个习惯比你会背十种写法都管用。
阅读完成 · 觉得有帮助？
