★ FEATURED ARTICLE 反转链表在力扣hot100里排第18位这个位置其实挺有意思的——热度不低难度不高但几乎每个刚开始刷题的开发都会在这道题上卡一会儿。我见过不少简历上写着“熟悉链表”的人现场写反转链表五分钟没写对也见过刷了好几遍的人被追问一句“递归版本里head.next.next head这行到底干了啥”就开始支支吾吾。链表这种数据结构很奇怪看起来就一个指针、一个循环的事真正写起来却特别容易暴露对引用、赋值、边界条件的理解是不是扎实。这篇文章我想把反转链表这件事拆开讲透为什么迭代要引入三个指针递归版本背后的执行过程是什么空链表和单节点为什么是高频翻车点以及从这一道题能延伸出哪些必刷的变体。适合三类人看刚开始刷hot100的初学者、准备面试想快速过一遍链表基本功的人、以及刷过题但想把自己的理解补完整的同学。内容不搞花活全部是可上手的代码、可复盘的思路、以及踩过才知道的坑。1. 反转链表到底在考什么1.1 链表的存储方式和数组的根本差异要理解反转链表先得理解链表为什么和数组不一样。数组在内存里是一段连续的空间你可以通过下标直接算出某个元素的地址访问第3个元素只需要一次加法运算时间复杂度O(1)。链表不是这样它的每个节点只存放两个东西当前的值以及“下一个节点在哪”的指针。链表没有下标的概念你手里只有一个头节点想找某个位置的节点只能从头开始一个个往后next过去。这带来一个非常重要的结果数组反转有天然的“对称感”左右两个下标往中间走交换元素就行。链表反转没有任何对称性可言每个节点只认识自己的下一个节点没有谁认识自己的上一个节点。链表反转这件事本质上就是在不改变节点本身、不新建节点的情况下把所有next指针的方向统一掉头。所以这道题考的从来不是遍历考的是你对“指针重新指向”这个动作的理解以及对“操作顺序不能乱”的把握。用生活里的场景类比会更直观。把一条链想象成一群人手拉手排队每个人都只用右手牵着后面的人。现在要求整个队伍掉头队尾变成新队头队头变成新队尾。你能做的事只有让每个人松开右手换成牵前面那个人。这里面最容易被忽略的问题是——当你让A松开手去牵别人的时候B可能就掉队了所以你必须在松开之前先用手或者一个“标记”抓住B防止队伍断开。链表反转的迭代解法核心就这一件事。1.2 为什么面试官爱拿这道题做“标尺”反转链表在面试里出现频率高是因为它足够小、足够基础但内含的知识点密度不低。第一它考察你对引用类型的理解。C/C里是指针Java/Python/JavaScript里是引用不同语言写出来的细节有差异但核心概念都是“对象之间通过引用连接”。第二它考察赋值顺序。cur.next pre和pre cur这两行代码写反了或者中间漏存一个节点结果就完全不一样。第三它考察边界条件。空链表返回什么、只有一个节点返回什么、两个节点的情况能不能正确处理这些不是在写代码之前就能靠直觉自动规避的。我辅导过的同学里不少人能把这道题的代码背下来但一被问“为什么pre要初始化为null/None”就卡住。这个问题的答案其实是反转后的链表原头节点会变成新尾节点而尾节点的next必须指向空。如果pre一开始指向一个无关的节点原头节点的next就会指向那个节点链表就多出一截不该有的东西。所以不要以为初始化pre只是为了循环能用它本身就是最终答案的一部分。能把这种地方讲清楚的人才算真的掌握了这道题。2. 迭代解法三指针如何一步步完成反转2.1 三个指针是怎么想出来的我第一次写反转链表的时候想的很简单遍历一遍把每个节点的next指向前一个不就行了。但真写起来第一个问题就来了——假如当前节点是cur我要把cur.next指向它的前一个节点可我还没改它的next改了之后就不知道原本的“下一个节点”去哪了。于是你必须用一个变量先把cur.next保存下来这就是第三个指针存在的意义。迭代解法的三个指针分别是pre、cur、nxt也可以用prev、current、nextTemp这样的命名看个人习惯。它们的分工是pre当前节点的前一个节点初始化为空cur当前正在处理、需要改变next方向的节点nxt当前节点的原始后继用来防止断链。在每一轮循环里做的事情可以用一句话概括先抓住后继再回头指向前驱然后整体向前平移一格。这句话背下来比死记代码有用得多。我后来写其他链表题凡是涉及重新连接指针的地方脑子里浮现的都是“先抓住再改变再平移”这个动作。2.2 用一条四节点链表手推一遍下面用1 - 2 - 3 - 4 - None来做一次完整推演。初始状态pre Nonecur 1。第一轮nxt cur.next即nxt 2先把2这个节点“抓在手上”cur.next pre让1的next指向Nonepre curpre从None变成1cur nxtcur从1变成2。此时局部结构是None - 1而2 - 3 - 4 - None那段还没动。第二轮nxt 3cur.next pre2的next指向1pre 2cur 3。以此类推。到第四轮结束时链表变成4 - 3 - 2 - 1 - None此时cur已经变成None循环结束pre恰好指向4。最终返回的应该是pre而不是head因为head也就是原来的节点1已经被移动到链表尾部了。很多新手在这里犯错返回head结果只返回了一个孤零零的尾节点。完整代码class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverseList(head: ListNode) - ListNode: pre None cur head while cur is not None: nxt cur.next # 先保存后继 cur.next pre # 改变方向 pre cur # pre 前移 cur nxt # cur 前移 return pre如果是Java逻辑一模一样只是类型声明不同public ListNode reverseList(ListNode head) { ListNode pre null; ListNode cur head; while (cur ! null) { ListNode nextTemp cur.next; cur.next pre; pre cur; cur nextTemp; } return pre; }这里有个细节值得强调nxt cur.next必须在cur.next pre之前执行。原因之前说过但这句值得再重复一遍因为它是所有链表指针操作的通用法则——你还没有把后继节点用变量保存起来之前绝对不能先动当前节点的next。类似的情况在“删除链表节点”“合并链表”里都会遇到养成了“要先保存再修改”的习惯很多题会顺手很多。2.3 迭代解法的复杂度与边界表现时间和空间复杂度是这道题的标准答案时间复杂度O(n)因为每个节点只被访问一次空间复杂度O(1)因为只用了三个额外变量没有随链表长度增长的额外空间。边界情况在迭代解法里其实是被循环条件天然处理掉的。如果head是空链表cur None循环根本不会进入直接返回pre也就是None符合“空链表反转后还是空链表”的预期。如果head只有一个节点循环执行一次cur.next pre会让这个节点的next指向None等同于没有实际变化返回pre也还是这个节点。所以学会了迭代写法之后建议顺手在纸上确认一下这两个边界基本就能保证提交不踩坑。3. 递归解法把问题缩小到只剩两个节点3.1 递归的思考方式不是模拟而是信任很多人觉得递归版的链表反转难懂是因为试图在脑子里展开整个调用栈指望模拟到底。这个方法在链表长度短的时候还能忍链表一长大脑很快就会过载。递归题的正确打开方式是“信任”先假设递归调用已经帮你解决了规模更小的问题你只负责处理当前这一层需要做的事。反转链表的递归定义可以写成这样reverseList(head)的结果是先把head后面的整条链表反转再把head接到反转后链表的末尾。后面这一整条链表反转后它的头节点是newHead它的尾节点恰好是head.next。这是什么概念呢原链表head - next... - tail反转以后是head - next... - tail其中newHead tail而原链表的第二个节点head.next在反转后变成了整条链的最后一个节点。所以“把head接到末尾”这个操作其实只要让head.next.next head再让head.next None就行。递归的终止条件有两个缺一不可head is None空链表不需要反转head.next is None只有一个节点反转后还是它自己。递归版本代码def reverseList(head: ListNode) - ListNode: if head is None or head.next is None: return head new_head reverseList(head.next) head.next.next head # 让后继节点指回当前节点 head.next None # 当前节点的next置空作为新尾节点 return new_head3.2 用两个节点和三个节点分别模拟递归执行先从最简单的“两个节点”开始1 - 2 - None。调用reverseList(1)因为1.next不是None继续递归reverseList(2)。节点2满足终止条件head.next is None直接返回2。回到节点1这一层new_head 2此时执行head.next.next head等价于让2的next指向1再执行head.next None让1的next置空。于是得到2 - 1 - None返回new_head2。这个过程很干净不绕。再看三个节点1 - 2 - 3 - None。调用reverseList(1)内部调用reverseList(2)内部又调用reverseList(3)。节点3满足终止条件直接返回3。回到节点2这一层new_head 3head是2head.next是3执行head.next.next head后3的next变成2再执行head.next None2的next变成None。此时局部反转结果是3 - 2 - None返回3。回到节点1这一层new_head还是3head.next.next head让2的next变成1再把1的next置空。最终得到3 - 2 - 1 - None。从模拟里能看出来递归版本的核心动作其实只有两个head.next.next head和head.next None。前者做的是“两个节点之间的掉头”后者做的是“让当前节点成为新链表末尾”。递归的作用只是让这个动作从链表的尾部一层一层往回传导。理解了这一点递归版本就不再是“魔法”了。3.3 两种解法怎么选择迭代和递归在时间复杂度上一样都是O(n)主要分歧在空间复杂度。迭代只用O(1)空间递归因为要占用系统调用栈空间复杂度是O(n)。在链表特别长的时候递归还有栈溢出的风险。那为什么还要学递归写法因为面试官喜欢问因为这题是理解更复杂递归问题的跳板也因为递归写法代码量更少、更接近数学定义在讨论思路时有它独特的表达力。我个人的建议是笔试和提交代码用迭代稳且省空间面试聊思路的时候把递归也讲一遍重点讲清楚head.next.next head为什么能让后继节点掉头以及为什么最后要置空next。这样既能展示你理解边界条件和空间复杂度又能说明你掌握两种不同思维路径。不少面试官会在你说出“递归栈空间是O(n)”之后露出满意的表情因为他们想听的就是这句话。4. 边界条件与错误写法实录4.1 三个必须提前测的输入链表题最常见的问题不是算法不会而是边界没处理。反转链表至少需要测试三种输入空链表、单节点链表、两个节点的链表。空链表如果返回的是None正常单节点返回原节点正常两个节点输入1 - 2反转后必须是2 - 1这个最考验操作顺序。再往上可以测三个节点、四个节点的常规情况以及很长的链表中是否有环或错误指向。有些人还会纠结一个问题链表长度可能是奇数还是偶数反转链表不依赖奇数偶数所以这个问题其实不用考虑。但“链表中是否有环”倒是值得留意如果输入自带环迭代版本会死循环不过力扣的标准输入里不会出现这种情况面试的时候提一句“如果输入可能有环需要先检测环”反而加分。4.2 高频错误速查表这里的错误都是我实际见过、自己也犯过的整理成一张速查表更实用错误现象根本原因修复方式返回结果只剩一个节点在修改cur.next前没有保存nxt导致链表断掉务必先用nxt暂存cur.next运行超时或内存异常反转后链表成环比如1和2互相指向检查每一层递归中head.next None是否执行返回了原来的head节点忘记原head在反转后变成尾节点迭代返回pre递归返回new_head测试单节点时出错递归终止条件漏了head.next is None补齐两个终止条件迭代版本不进入循环返回Nonecur head写成了cur head.next确认初始化指向头节点每一个错误的修法都不难难的是快速定位。我建议提交之前先把自己代码里的变量名念一遍确认每个变量在每一轮循环结束后的值都和预想一致。这个方法听着笨但确实是排查链表题最快的方式。4.3 调试链表题的三个实操技巧技巧一打印节点值。普通变量可以打印链表节点也可以。在迭代循环里打印当前节点是什么下一步要去哪while cur: print(fcur{cur.val}, pre{None if pre is None else pre.val})注意打印前不要真的访问None节点否则调试还没开始程序就先崩了。技巧二画箭头图。不需要画得多好看重点是区分“节点的val”和“节点之间的连接关系”。很多错误比如环、断链、返回错误节点用一支笔画一遍就能发现。我在纸上写递归题的推演过程后往往会发现错误出现在“递归返回后忘了置空next”这一类地方。技巧三用小样例单步走。把链表缩短到三个节点手动在debugger里一行行走下去看每一步变量变化。单步走几次之后你对三指针运作的理解会比看一百遍题解都深。尤其注意的是在递归版本里单步走会走进很多层调用所以可以只在最内层返回时设置断点观察回溯阶段的行为。5. 从一道题到一类题反转链表三大变体5.1 反转区间从任意位置穿针引线反转整条链表会了力扣第92题就问只反转从left到right这一段其余部分保持原样。这个问题难在两处定位要反转的起始位置以及反转完之后和前后部分重新接上。思路是先用一个dummy节点避免处理头节点变化的麻烦然后让pre走到left位置的前一个节点。接下来把pre.next到right位置的这一段反转每次把当前节点后面的节点“头插”到pre的后面走right - left次。def reverseBetween(head: ListNode, left: int, right: int) - ListNode: dummy ListNode(-1) dummy.next head pre dummy for _ in range(left - 1): pre pre.next cur pre.next for _ in range(right - left): nxt cur.next cur.next nxt.next nxt.next pre.next pre.next nxt return dummy.next这里用头插法比用三指针整段更自然的点在于不需要单独把中间那段拆出来再拼回去。每轮操作都把当前处理的节点提到pre后面循环次数固定边界条件更容易控制。做这道题时建议先画图pre - 1 - 2 - 3 - tail中反转1 - 2 - 3每一轮头插后的状态变化用箭头画一遍很快就能理解。5.2 K个一组反转分组的本质是多次局部反转力扣第25题把变体再升级一步每K个节点一组组内反转组间顺序不变不足K个的保持原样。这道题写熟练的人反而会比反转区间更多一些因为思路是“先检查够不够一组够就反转这一组然后移动到下一组”。实现中要注意的是每一组反转完之后要把反转后的组头和组尾分别接到上一组的尾和下一组的头。因此组内反转结束后原始组头反转后成为组尾的next必须指向下一组前驱的next指向反转后的新组头。def reverseKGroup(head: ListNode, k: int) - ListNode: dummy ListNode(-1) dummy.next head prev dummy while True: cur prev for _ in range(k): cur cur.next if not cur: return dummy.next group_head prev.next nxt_group cur.next last None cur group_head while cur ! nxt_group: temp cur.next cur.next last last cur cur temp group_head.next nxt_group prev.next last prev group_head这段代码有个很容易闷住的地方prev group_head而不是prev last。想想为什么——反转之后last是这一组的头节点group_head是这一组的尾节点下一组的前驱应该是这一组的尾节点所以prev要更新为group_head。如果写成prevlast下一组就会从错误的节点开始找。这个小坑考试时栽过的人不在少数。5.3 反转思想在业务代码里的影子刷题不能只为了过笔试。反转链表的本质是“改变一个顺序结构中的遍历方向”在真实系统里到处都有类似需求。比如常用的一些缓存淘汰策略其中就涉及把最近使用的节点提到链表头部、把最久不用的节点移到尾部这里的“掐断、重连”操作和链表反转高度相似。再比如很多编辑器里的“撤销/重做”功能、文档的历史版本回退、浏览器的前进后退栈背后都是顺序结构的状态调整和链表指针重连是同一类思维。我自己的感受是链表这类题最大的价值不是让你记住某个模板而是反复训练“你到底知不知道下一步该指向谁”这个意识。能理清反转链表的指针变化再去写LRU缓存、写区间反转、写K个一组就都只是同一套动作在不同场景下的变体。这道题我前后写过不下二十遍每次刷到相关变体题还是会先从反转的基础代码推起。不要嫌基础题简单基础题的细节真正吃透以后给后面的难题省的时间远比当初卡在这一题上的时间多。
阅读完成 · 觉得有帮助？
