反转链表这个题我面试里见过别人做自己也动手写过后来工作中处理消息队列、匹配历史回溯、缓存淘汰链表调整时又一遍遍遇到同样的结构操作。你搜这个标题大概率是在准备笔试面试或者刚学到链表这一章想搞清楚怎么把指针掉转方向到底是怎么回事。这篇文章我不想只贴一段代码而是把迭代、递归、头插三种思路以及边界条件、调试方法、进阶变体都讲清楚。不管你是刚入门、正在背题还是想彻底搞懂原理往下读都能有收获。先说个基础概念链表是一种线性结构每个节点存一个值和指向下一个节点的指针单向链表只能从头往后走没有回头路。反转的目标就是把原来 head-A-B-C 变成 head-C-B-A注意这里的 head 本身不是节点它是第一个节点的引用。很多人一开始纠结头节点会不会丢实际上反转后返回的是原链表的最后一个节点作为新头。我见过不少人在视频课里能跟着写代码一闭卷就卡壳根本原因是没搞清指针赋值顺序。这篇文章会慢慢拆解——从最朴素的一个一个摘下来放到新链表头部的思路讲起再过渡到递归和进阶变体中间穿插我踩过的坑、测试技巧和排查方法。1. 为什么反转链表这么经典1.1 题目到底在问什么先给一个最朴素的定义输入一个单链表的头节点 head将链表反转返回反转后的头节点。输入: 1 - 2 - 3 - 4 - 5 - null 输出: 5 - 4 - 3 - 2 - 1 - null不涉及额外空间通常要求时间复杂度 O(n)、空间复杂度 O(1)。递归法因为会有调用栈空间是 O(n)但很多面试场景下也是被接受的因为递归写起来直观只要讲清楚原理就行。1.2 它考察的不只是背代码反转链表是所有链表题目的地基。你可以用它练出三个关键能力指针操作是否扎实、对边界条件是否敏感、在复杂变体里能否快速抽象。实际工作中LRU 缓存淘汰、撤销操作栈、双端遍历逻辑里都藏着把相邻节点反过来接的影子。这个题刷透了后面做反转区间、K 个一组反转、回文链表判断都会顺很多。2. 方案选型迭代、递归、头插怎么选2.1 三类主流思路对比先把三个方案的名字和直观感受放一起方案核心动作空间复杂度写代码的直觉难度迭代三指针每步保存后继改当前节点指向前驱O(1)顺序清晰容易理解递归先递到末尾归的过程中翻指针O(n)理解门槛高写起来最短头插新链表头部依次插入原链表节点O(1) 或 O(n)有哨兵节点后很直观2.2 我为什么通常倾向迭代迭代法没有调用栈性能稳定面试时也最容易讲明白——因为它每一步的物理动作都有画面感。我面试别人的时候候选人如果能画出三个指针同步移动的过程我基本觉得他有实质理解。实际生产环境里链表的长度偶尔会到几万甚至更多递归法在这种深度下可能直接爆栈所以默认选迭代是更稳妥的工程习惯。2.3 递归能带来的编程美感不过递归也有它的价值。它的代码可以在几行内完成反转逻辑非常干净先反转后续子链表然后把当前节点接到子链表的尾巴上。我建议你至少要会写因为很多公司的面试官会追问你会几种方法这时候只答一种就显得单薄。理解了递归对分治思想、二叉树翻转这些后续题目也有帮助。3. 三种主流实现逐行拆解3.1 迭代三指针法先定义链表节点。假设用 Python 的类来表示class ListNode: def __init__(self, val0, nextNone): self.val val self.next next接下来是核心代码def reverse_list(head): prev None curr head while curr is not None: nxt curr.next curr.next prev prev curr curr nxt return prev可能有人会觉得这个代码短到不需要解释但我还是要强调三行关键动作nxt curr.next保存下一个节点。因为下一步我们就要修改curr.next如果先改再找后继原来的后继就找不到了。curr.next prev让当前节点倒过来指向它前面的节点。prev curr和curr nxt两个指针一起后移进入下一次循环。走一遍流程给一个链表 1 - 2 - 3 - null初始prev nullcurr 1第一轮nxt 2把 1.next 指向 nullprev 1curr 2。现在链表后半段是 2 - 31 是独立的尾巴也就是反转后的末尾。第二轮nxt 3把 2.next 指向 1prev 2curr 3。此时 3 - null 还没处理但 2 - 1 已经接好。第三轮nxt null把 3.next 指向 2prev 3curr null。循环结束prev 就是 3这才是反转后的头。3.2 递归法递归的代码很短但第一次看到的人十有八九会懵def reverse_list(head): if head is None or head.next is None: return head new_head reverse_list(head.next) head.next.next head head.next None return new_head理解它的两个关键递归的返回值是整个子链表反转后的新头。比如原链表 1 - 2 - 3 - 4在递归到最深处时处理的是只剩节点 4它直接把自己返回。head.next.next head这一句是让当前节点的后继节点把指针指回当前节点。举个例子当递归栈从 4 回到 3 时head 是 3head.next 是 4之前的 4 返回给上层时已经带着自己的新连接我们只需要让 4.next 指向 3再把 3.next 置为 null防止成环。很多教程会画复杂的递归展开图我自己的经验是先别盯整体只看一个节点 一个已经反转好的子链表如何接上。只要这一环通了递归的自然规律会自动把整个链表翻过来。3.3 头插法头插法的名字听着陌生但思路很朴素我建一个新的头然后不断把原链表头部的节点摘下来插到新头的后面最后得到的就是反转结果。用一个哨兵节点可以省掉很多空指针判断def reverse_list(head): dummy ListNode(0) curr head while curr: nxt curr.next curr.next dummy.next dummy.next curr curr nxt return dummy.next这里dummy是哨兵它的 next 始终指向已经反转好的链表头。每次新摘下来的节点都强制插到 dummy 后面相当于每次都在已反转区间的头部动刀。这个方法在某些进阶题比如反转区间里非常有用因为你可以显式控制把节点插到哪个位置。4. 实操验证从构造链表到测试用例4.1 辅助函数数组转链表、链表转数组写算法题最怕的是代码跑完没有反馈。我建议你准备两个辅助函数一个是把数组转成链表另一个是把链表打印成数组或字符串。这样每次改完代码能立刻看到输入输出对不对。def build_linked_list(values): if not values: return None head ListNode(values[0]) current head for v in values[1:]: current.next ListNode(v) current current.next return head def linked_list_to_list(head): result [] while head: result.append(head.val) head head.next return result为什么要这两个函数因为手写链表节点的过程很容易出错而数组是我们最熟悉的容器。你再也不用每次都在纸上画十几个箭头。比如输入[1,2,3,4,5]转成链表调用 reverse再转回数组输出就能肉眼验证。4.2 边界测试我写算法题的一个习惯核心用例通过之后必须单独跑四组边界用例空链表输入[]输出应该也是[]。单节点链表输入[1]反转后还是[1]。双节点链表[1,2]反转成[2,1]这一步最容易发现要不要处理 next。大量节点比如一万个节点的链表用来验证迭代法和递归法的空间段是否稳。如果这四组全部通过这个 reverse_list 函数的正确性就有很大把握了。不要只盯着中间的普通用例很多隐藏 bug 恰恰在边界触发。4.3 在本地断言逻辑如果你用的是 Python最简单的验证方式就是 assertassert linked_list_to_list(reverse_list(build_linked_list([]))) [] assert linked_list_to_list(reverse_list(build_linked_list([1]))) [1] assert linked_list_to_list(reverse_list(build_linked_list([1, 2]))) [2, 1] assert linked_list_to_list(reverse_list(build_linked_list([1, 2, 3, 4, 5]))) [5, 4, 3, 2, 1] print(all passed)实测下来这一组断言能覆盖大部分基础问题。如果你在某个在线题库里做也能自己构造几个自定义用例提前发现问题而不是等提交失败才改。5. 常见问题与排查实录5.1 链表反转后死循环这是最经典的问题写迭代法时如果顺序错了比如先改curr.next再把nxt curr.next那 nxt 拿到的是已经被改过的prev链表就会变成回环。排查办法非常朴素把链表转成数组打印出来如果程序一直不结束或者出现重复数字基本就是成环了。更稳妥的防范方式是永远先备份后继。我自己的口诀是改向之前先存一下 next。这个习惯在反转区间的题目里更加重要因为那里的指针交错更复杂。5.2 反转后末尾节点没有指向 null迭代里prev初始化为null所以第一个节点反转后能正确指向 null递归里处理完当前节点后要显式执行head.next None否则会形成环。很多初学者在这件事上吃过亏尤其是递归以为head.next.next head就够了忘记把原来的 next 断掉。5.3 递归栈溢出递归法在节点数较多时比如十万个节点可能导致调用栈溢出程序直接崩溃。生产环境中如果数据结构是链表且长度不可控我会优先选择迭代法。面试时如果选了递归最好主动提一句递归在链表过长时有爆栈风险我可以改成迭代实现这比被面试官追问时再说要体面得多。5.4 反转过程中丢节点这通常出现在对nxt的使用不熟练时。你要意识到一旦curr.next被重新赋值原来那个节点就断了线。想接回来只能靠事先保存的nxt。我做题时习惯在每次修改指针前先用眼睛确认三件事prev 是谁、curr 是谁、nxt 是谁。只要三指针状态清晰丢节点的情况基本不会发生。5.5 调试技巧画小图 打印状态链表题是少数画图比写代码更管用的题。遇到复杂反转区间我会在纸上画一个三个节点的小链表然后同步手动执行每一轮循环记录每次修改之后的连接状态。这个动作看着笨但真的能救急。调试代码时可以在循环里临时加一行print(prev.val if prev else None, curr.val if curr else None, nxt.val if nxt else None)看一眼每一步移动是否符合预期。6. 进阶变体反转区间与 K 个一组反转6.1 反转从 left 到 right 的区间很多面试官不会让你直接反转整个链表而是问反转从第 m 个节点到第 n 个节点的部分其余不变。比如1 - 2 - 3 - 4 - 5反转区间[2, 4]结果是1 - 4 - 3 - 2 - 5。设计思路也很标准先让指针跑到区间前一个节点然后利用头插法把区间内每个节点插到边界节点后面。我写这个题的参数比较讲究先用哨兵节点统一操作避免 left 1 时头节点需要特殊处理。def reverse_between(head, left, right): dummy ListNode(0) dummy.next head prev dummy for _ in range(left - 1): prev prev.next curr prev.next for _ in range(right - left): nxt curr.next curr.next nxt.next nxt.next prev.next prev.next nxt return dummy.next这段代码的妙处在于curr始终是区间内第一个节点每次把curr的下一个节点摘出来让它指向区间目前的新头prev.next然后更新prev.next指向这个新节点。这样循环right - left次区间就反转完成。我在本地跑[1,2,3,4,5]left2right4拿到[1,4,3,2,5]和预期一致。6.2 K 个一组反转链表这题在多数大厂题库里属于 hard 等级但一个清晰的心智模型是把整个链表切成若干个长度为 K 的块每个块内部反转再把这些块重新连接起来。实现时通常先算出链表长度确定需要处理几组然后复用反转区间的核心逻辑每一组的末尾再接上下一组的头部。这里我不建议把 length 只用来统计而不参与逻辑。真正的坑点在于最后一组不足 K 个时保持原样。所以我会记录每一组的头和尾反转完一组后把 prev 指针移到组尾再继续下一组。这个过程代码量比单纯反转大但如果你前面把反转区间吃透了它只是循环调用区间反转而已。6.3 进阶思路的共性总结不管是最基础的反转还是反转区间、K 个一组底层都在做类似的事找到正确的边界、备份后继、修改指向。很多人刷题时贪多实际没必要。你只要把三种基础实现练到肌肉记忆再掌握哨兵节点和指针备份两个习惯进阶题就不会再有看不懂答案的挫败感。7. 动手练习的建议7.1 先手写再上机我对自己带过的人有个固定建议拿到链表题先在白纸上画链表再用手指模拟指针移动能完全走完一个简单用例之后再开始写代码。反转链表这个题尤其适合这么练因为它逻辑简单、变体丰富练一次等于把所有指针操作的基础都过了一遍。7.2 按自己的节奏拆小步骤如果你觉得递归难没必要硬啃。先用迭代法刷三到五遍能无输出写对之后再带着子问题视角去理解递归最后那两行代码。我见过太多人第一天就纠结递归白白消耗信心。一步一步来反而学得快。7.3 用自动化测试给自己兜底在实际开发里我几乎不会在没有单元测试的情况下修改链表相关代码。你自己练习时也可以把构造、反转、断言三个步骤写在一个脚本里每次改动都跑一遍。我自己的习惯是保留一个test_reverse.py里面十几个断言用例任何改动后一条命令全部验证心里特别踏实。7.4 性能考量与实际应用场景虽然刷题时链表长度不会太大但在真实系统中比如实现一个 LRU 缓存、维护一个最近使用列表反转/重排链表的操作不会太频繁但仍需要保证在链表较长时不会栈溢出。这也是我反复强调默认用迭代的原因。如果你正在做一个消息队列或回退系统这种底层的稳定性会直接影响线上服务。8. 写在最后的一些心里话我刚开始学链表反转时也觉得代码就几行没什么可研究的。后来被 bug 狠狠教训过几次——一次是写 LRU 时把 prev 和 next 接反线上出现死循环一次是递归翻转长链表生产环境直接栈溢出。从那以后我养成了两个习惯任何指针修改前一定保存 next任何递归写法都先评估数据规模。这两个习惯让我少加了无数个班。如果你现在正卡在这个题目上别灰心。反转链表几乎是所有链表问题的第一道门槛翻过去之后后面的反转区间、链表相交、环形链表都会变得顺畅得多。你先用迭代法写十遍再尝试递归再自己写几个辅助函数做测试彻底跑通过一轮之后这个知识点才算真正属于你。希望这篇文章能帮你少走一些我当年走过的弯路。
