## 1. 为什么一道反转链表能让人卡一晚上先看清链表的脾气 我第一次刷力扣第206题“反转链表”时代码写出来不到十行可运行结果要么空指针要么链表直接断成两截。后来复盘才发现问题根本不在“反转”这个动作上而在我对链表的基本结构缺乏肌肉记忆。链表这玩意儿画图谁都看得懂一落代码全是细节。 ### 1.1 数组是“物理邻居”链表是“逻辑邻居” 数组在内存里是连续一块你拿到了首地址就能靠下标直接算出第n个元素在哪。链表完全不同每个节点是散落的内存对象节点之间靠“引用”串起来。用一句大白话概括数组的邻居是物理上挨着的链表的邻居只是“逻辑上认了这门亲”。 这对解题意味着两件事。第一访问第n个节点必须从头逐个next走过去时间复杂度O(n)没有捷径。第二修改链表结构时你改的其实是指向关系而不需要搬动任何数据。反转链表之所以容易写错是因为我们习惯用“值”思考问题但链表题要求你全程用“引用”思考问题。 ### 1.2 单链表的基本形态与节点定义 单链表里每个节点只存两样东西当前的值val以及指向下一个节点的引用next。最后一个节点的next指向None表示“后面没东西了”。 用Python定义节点非常简洁 python class ListNode: def __init__(self, val0, nextNone): self.val val self.next next如果你用Java或C概念完全一致只是Java里是引用类型C里是指针。面试时手写链表的考点从来不是谁能背出这个类定义而是你能不能边写边说出“next存的是下一个节点的地址”这句话。我见过不少同学把节点设计成带prev的双向链表还理直气壮说是“为了后面反转方便”。先别急着上复杂度单链表是基础双向、循环都是在它之上加字段而已。连单链表的引用都玩不顺直接上双向链表只会让错误翻倍。1.3 链表解题的通用思维盯住引用不盯住数据链表的操作核心只有两件事接住和断开。接住就是先保存某个节点的引用断开就是让某个节点的next重新指向新的目标。顺序永远是先接住再断开。这个原则贯穿所有链表题包括反转。你可以把链表想象成一列火车每节车厢只知道自己后面那节是谁。现在要整列火车掉头你不能直接掰车身只能一节一节改挂钩。改挂钩最忌讳的是先把A车厢的挂钩松了却忘了B车厢已经跟着跑没了。2. 从零手写单链表基础操作比想象中更值得抠细节很多人一上来就刷反转链表结果连“在指定位置插入节点”都写不利索。我建议把基础操作先完整走一遍哪怕只是在自己电脑上跑通一次后面做所有链表面试题都会顺手很多。2.1 用一个数组快速构建链表写链表题最烦的就是构造测试数据。日常刷题时我习惯用一段工具代码把数组直接转换成链表def build_linked_list(arr): dummy ListNode() # 用哑节点省去头节点特判 cur dummy for val in arr: cur.next ListNode(val) cur cur.next return dummy.next这段代码里有个小技巧用一个dummy哑节点占住开头循环结束后直接返回dummy.next。好处是整个构建过程不需要单独判断“这是不是第一个节点”代码少一个分支就少一个出错点。后面在反转区间、删除节点时这个思路会反复出现。2.2 遍历、计数、输出三步走遍历链表是最基本的操作也是后面所有算法的地基。一个简单的打印函数长这样def print_linked_list(head): res [] cur head while cur: res.append(str(cur.val)) cur cur.next print( - .join(res))计算长度同理只要把循环里的收集动作换成累加即可。这里我想强调一个容易忽略的细节遍历时一定要用一个临时变量cur去接head绝对不要直接移动head。很多人觉得“反正函数结束了”但一旦你的链表同时被别的地方引用擅自移动head就会造成不可控的副作用。养成“不裸奔head”的习惯能帮你躲掉很多莫名其妙的bug。2.3 插入和删除先把引用接住再拆引用在单链表中在第i个位置插入节点的标准步骤是先找到第i-1个节点prev然后新节点指向prev.next最后prev.next指向新节点。代码长这样def insert_at(head, index, val): dummy ListNode(nexthead) prev dummy for _ in range(index): if not prev: raise IndexError(index out of range) prev prev.next new_node ListNode(val) new_node.next prev.next prev.next new_node return dummy.next注意代码里两行赋值的顺序不能反过来。如果先执行prev.next new_node原来的prev.next就被弄丢了新节点后面就接不上原来的链表了。这就是我上一节说的“先接住再断开”。删除节点时同样如此先让prev.next跳过目标节点直接指向目标节点的next。此时目标节点虽然还存在但已经没有任何节点指向它Python的垃圾回收会处理掉它。2.4 一个容易忽略的点头节点要不要单独维护单链表里“头节点”是很特殊的位置因为只有它没有前驱。一旦头节点被修改或删除整个链表的入口就变了。很多人写插入、删除时对头节点做一堆特判非常痛苦。我更推荐的是永远用一个dummy节点顶在前面。dummy.next才是真正的头节点。这样无论是插入第0位还是删除第0位都和其他位置用同一套逻辑处理。别小看这个习惯它能让你的反转链表II代码简洁非常多。3. 迭代反转链表三根指针的换位舞回到力扣206这道题。题目描述很简单给你单链表的头节点head请你反转链表并返回反转后的链表头节点。这是一个非常经典的原地反转问题。不能新建数组不能用额外空间只能改节点之间的next指向。3.1 迭代解法的核心思路迭代解法需要维护三个指针prev已经反转好的部分链表的“头”初始为Nonecur当前要处理的节点初始为headnext_temp提前保存cur的下一个节点防止丢失每一步做的事情是先把cur.next保存到next_temp然后让cur.next指向prev接着prev和cur各自向前移动一位。为什么必须先保存next_temp因为一旦cur.next改成prev原来后面的链表就和cur断开了。如果不提前记住它循环就找不到下一个要处理的节点了。3.2 代码与逐步推演以1→2→3→4→5为例def reverse_list(head): prev None cur head while cur: next_temp cur.next cur.next prev prev cur cur next_temp return prev假设链表是 1 - 2 - 3 - 4 - 5逐步推演如下初始状态prev Nonecur 1第一步把2存进next_temp让1.next指向Noneprev变成1cur变成2。此时链表一会儿是 1 - None一会儿是 2 - 3 - 4 - 5这两段在物理上是连着的但我们通过引用已经把它们看成两个部分了第二步把3存进next_temp让2.next指向1prev变成2cur变成3第三步把4存进next_temp让3.next指向2prev变成3cur变成4第四步把5存进next_temp让4.next指向3prev变成4cur变成5第五步next_temp变成None让5.next指向4prev变成5cur变成None循环结束返回prev也就是新链表的头节点5很多人卡在“为什么返回prev而不是cur”。因为循环结束时cur已经跑到None去了真正反转后的头节点是最后一个被处理的节点也就是prev。这个细节面试时几乎必问。3.3 边界情况与复杂度边界情况一共有三种必须逐一确认链表为空head为None循环根本不进入直接返回None正确。链表只有一个节点cur不为None进入循环next_temp为Nonecur.next指向Noneprev变成这个节点cur变成None返回这个节点正确。链表有两个节点 1 - 2第一步后变成 2 - 1 - None正确。时间复杂度O(n)空间复杂度O(1)。这是链表反转的最优复杂度。4. 递归反转链表从最后一个节点开始倒着改指向迭代解法已经足够优秀但递归解法能帮你从另一个角度理解链表结构而且面试中经常被追问。理解递归版本之前你得先接受一个“反直觉”的事递归走到的是链表末尾而不是开头。4.1 递归的直觉先处理子问题假设链表是 1 - 2 - 3。如果我能把 “2 - 3” 这一段反转好得到 “3 - 2”那么我只需要让 2 指向 1让 1 指向 None整个链表不就反转完了吗这就是递归的思路先调用函数反转“去掉第一个节点之后的剩余链表”然后把当前节点接到反转结果后面。边界条件是链表为空或只有一个节点时不需要反转直接返回。我个人的体会是递归解法千万不要在脑子里硬展开每一层调用那样会晕。你要做的只是相信“这个函数能反转传入的链表”然后把当前这一步接好就行。4.2 递归代码与调用栈分解def reverse_list_recursive(head): if not head or not head.next: return head new_head reverse_list_recursive(head.next) head.next.next head head.next None return new_head以 1 - 2 - 3 - 4 为例调用过程如下调用 reverse(1)head.next存在于是调用 reverse(2)调用 reverse(2)head.next存在于是调用 reverse(3)调用 reverse(3)head.next存在于是调用 reverse(4)reverse(4) 进入边界条件因为 4.next 为 None返回4回到 reverse(3)new_head 4执行 3.next.next 3也就是 4.next 3再执行 3.next None返回4回到 reverse(2)new_head 4执行 2.next.next 2也就是 3.next 2再执行 2.next None返回4回到 reverse(1)new_head 4执行 1.next.next 1也就是 2.next 1再执行 1.next None返回4关键动作是head.next.next head。head.next是本来已经反转好的子链表的新尾节点让它指向head等于把当前节点挂到反转好部分的后面。每次递归返回的new_head始终是同一个节点也就是原链表的最后一个节点新链表的头。4.3 迭代和递归怎么选一张表看懂维度迭代递归思路方向从前往后依次反转从末尾往前倒着接空间复杂度O(1)O(n)递归调用栈占空间代码量稍多但直接精简但难理解边界处理需要细心控制循环边界放在开头好处理面试风险不容易写错容易在“head.next.next”上卡壳链表超长时放心跑可能栈溢出如果你面试的目标是稳妥我更建议优先迭代。如果你对递归理解到位可以在面试官追问时展示递归版本。4.4 递归方案的隐藏限制递归方案有个非常现实的问题当链表长度达到几千甚至上万时Python默认递归深度限制会导致崩溃。这不是“反转算法错了”而是递归深度超出了解释器的承受范围。所以我平时练习时会刻意两种解法都写一遍但在生产级代码或超长链表的压力测试里只会用迭代。理解递归能帮你打通“子问题”的思路但它不一定是最适合落地的方案。5. 变体题反转链表II和K个一组翻转力扣206只是开了个门真正把反转动作用到复杂场景的是这两道变体题反转链表II以及K个一组翻转链表。它们都建立在“局部反转”的基础上但多了一些接回去的步骤。5.1 反转链表II锁定区间接回原链表题目要求反转从第left个节点到第right个节点的部分其他部分保持不变。比如 1 - 2 - 3 - 4 - 5left2right4结果是 1 - 4 - 3 - 2 - 5。核心思路分三步用dummy节点顶住头部防止left1时头节点变化。找到left的前一个节点prev以及left位置的节点cur。从left到right这一段用迭代法逐个反转反转完后prev.next指向反转后的头原区间头节点的next指向right后面的节点。写起来是这样的def reverse_between(head, left, right): dummy ListNode(nexthead) prev dummy # 第1步走到 left 前一个节点 for _ in range(left - 1): prev prev.next # 第2步开始反转 cur prev.next for _ in range(right - left): next_node cur.next cur.next next_node.next next_node.next prev.next prev.next next_node return dummy.next注意这里没有引入真正的区间尾部变量而是用“把后一个节点不断前移”的方式完成反转。每次迭代把next_node从原位置拎出来插到prev后面。这个写法比直接写三指针更不容易绕晕我实测非常稳推荐你记下来。5.2 K个一组翻转链表分组反转的标准套路这道题要求每隔k个节点反转一组如果最后一组不足k个则不反转。比如链表 1 - 2 - 3 - 4 - 5k2结果是 2 - 1 - 4 - 3 - 5。标准解法是递归迭代混合先往右看k个节点够数就反转这一段然后递归处理后面的部分。def reverse_k_group(head, k): cur head count 0 while cur and count k: cur cur.next count 1 if count k: cur reverse_k_group(cur, k) while count 0: next_node head.next head.next cur cur head head next_node count - 1 head cur return head这套代码的思路是先确认当前组有k个节点递归先把后面的组反转好拿到连接点cur然后从第一个节点开始逐个把它接到cur前面。本质上是把“反转整个链表”拆成了“反转一组再接上后面已反转的部分”。5.3 变体题的共同套路先拆后接做了三道反转相关题目后你会发现套路极为统一遇到头节点可能变化的情况先建dummy锁定要反转的区间记录区间前驱和后继用迭代法在区间内反转把区间反转后的头和尾接回到原链表这种“先拆后接”的思路不仅适用于链表反转也适用于所有链表结构调整题。我建议你别急着背代码先在纸上画出四个关键节点区间前的前驱、区间第一个节点、区间最后一个节点、区间后继。把这四个节点画清楚代码就是顺着它们连起来的。6. 链表题经常挂的五个坑和我的调试习惯写链表题最痛苦的不是想不明白思路而是代码看着全对跑起来就崩。我把自己踩过的坑系统整理了一下尤其建议初学链表的同学逐条对照。6.1 空指针访问null永远是第一杀手报错信息通常长这样AttributeError: NoneType object has no attribute next。原因多半是在while循环里没有判断cur是否为None就直接访问cur.next。我检查代码的方法是每写一个cur.next前面一定确认cur不为空。反过来也一样每写一个“cur为空就退出循环”的判断后面接的代码必须确保不会用到cur。6.2 引用丢失改谁之前先存谁这是新手最常见的错误。反转链表时最危险的一行代码就是“cur.next ...”。一旦执行完cur原本的后继就断了。所以任何修改next的前一步都要用临时变量把原next保存下来。有一个通用口诀边改边存先存后改。哪怕你觉得自己已经记住了写完后最好再扫一遍检查每处next赋值之前是不是存在一个对应的next_temp。6.3 忘记断尾反转后不置空会带环反转单链表时原来的头节点会成为新链表的尾节点。如果忘了把它的next指向None它可能还指着原来的第二个节点而原来的第二个节点在反转后指向它于是整个链表带环。带环的可怕之处在于print链表时会死循环LeetCode提交时会超时而且这种bug特别难肉眼发现。我的经验是最小化测试单节点链表反转后一定要打印一遍确认只有一个节点两节点反转后打印确认两个节点且顺序反了。6.4 头节点变化的通用解法dummy node头节点一旦被修改整个链表的入口就变了很多逻辑都要特判。dummy节点一举解决了这个问题dummy.next永远指向真正的头节点。操作结束后返回dummy.next即可无论头节点怎么变都不用担心。我第一次意识到dummy厉害是在做反转链表II的时候。left1时没有dummy真不知道怎么写。用了dummy之后代码完全不需要为“left是不是第1个节点”单独开分支。6.5 我的调试路径与测试用例清单写链表的调试我不建议直接在LeetCode上盲试。先在本地跑这组用例把错误暴露得明明白白空链表head None只有一个节点head ListNode(1)两个节点1 - 2多个节点1 - 2 - 3 - 4 - 5带重复元素的链表长链表比如1000个节点验证没有死循环和栈溢出调试时我习惯每步打印链表。打印函数里加一个计数器超过一定次数就主动break这样能快速发现环的问题。等你把这些用例全部跑通再提交到力扣基本一次过。单链表的基础实现和反转看起来只是刷题必刷的一道小题但它锻炼的其实是“引用思维”和“边界思维”。我在实际工作中用LinkedList的场景并不多但链表题教会我的习惯——先接住、再断开先判断为空、再访问字段先保存现场、再修改状态——在写任何复杂代码时都是受用的。希望你也能把这几道题吃透别急着背答案每写完一次都试着用自己的话把指针移动过程讲一遍。