1. 链表题难在哪看着简单一写就崩如果你去翻各大平台的算法题库链表题永远是绕不过去的一块。数组题还能靠直觉蒙一蒙链表题一旦指针指错整段逻辑全部崩盘。我见过不少刷了几百道题的人回头写一个单链表逆序依然会出错——这太真实了因为链表题考察的不是会不会而是每一步指针的先后顺序、退出条件、返回哪个节点这些极容易被忽略的细节是否真的清楚。这篇文章准备聊三道经典链表题单链表逆序、链表成环检测、合并两个有序链表。这三道题覆盖了链表题目的三大核心思维指针重连、快慢指针、虚拟头节点。把这三板斧吃透绝大多数链表题你都能在几分钟内拆出解题框架而不是靠背题硬撑。适合谁看两类人。一类是刚开始刷算法、被链表搞得头大的人我会把每个指针为什么要这样走讲明白另一类是已经刷了不少题但总在链表上栽跟头的人我会把容易翻车的细节集中点出来。无论你现在处于哪个阶段这篇文章都值得完整读一遍。1.1 链表的最小单位节点和指针链表之所以叫链表是因为它的每个元素是一个节点ListNode节点里存着数据和指向下一个节点的指针。单链表的定义长这样class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextC/C 里的定义更直白struct ListNode { int val; struct ListNode *next; };单链表的本质是只知道下一个不知道上一个。你想拿到第 n 个节点必须从头节点往后遍历你想删除某个节点必须找到它的前驱节点。这个特性就是链表题和数组题最大的分水岭——数组通过下标随机访问你修改一个元素毫不影响其他元素链表修改一个 next 指针却可能让整个链条断掉或成环。所以刷链表题时你的脑子里不要想着很多节点而是想一条箭头串起来的链。代码里每一次赋值、每一次条件判断本质都是在操作箭头而不是操作实体。1.2 链表题最常见的翻车点我把这几年在面试和平时帮人改代码时看到的高频错误归纳了一下基本跑不出这几类遍历时先改了当前节点的 next结果下一个节点找不到了。这个错几乎每个新手都犯过本质是用下一步要用的信息去交换了当前的操作。while 循环条件写错。比如该判断while curr的地方写成while curr.next结果最后一个节点没处理或者该判断fast and fast.next的地方漏了后半段运行到一半直接空指针异常。返回值搞错。很多题最后要求返回链表头但因为移动指针把原来的头丢了最后返回了尾巴。忽略了空链表和单节点的边界情况。链表相关的题目边界条件经常是重灾区。空链表、只有一个节点、两个节点、尾部删除、尾部插入这些情况必须单独过一遍。为什么这些错误这么容易犯因为链表的操作本质上是对指针的重新指向这和数组的原地修改某个位置完全是两种心智模型。数组修改之后其他位置不关心你改了什么链表一旦你动了某个节点的 next它的后半段可能就和你失联了也可能被另一个指针同时引用着。这种牵一发动全身的特性要求你在写每一步之前都必须想清楚我改了这个指针还有谁在引用它它原来指向的那个节点我还需不需要再访问1.3 破局先画图再写码我每次给学生或者同事讲链表题都会先让他们做一件事在纸上把节点画出来每个节点画成一个方框next 画成箭头然后在箭头上标出每一步指针要移动的方向。这个过程看着笨但其实特别管用。你可以把节点看成口袋把指针看成手电筒。链表上的操作就是你在黑暗里用手电筒照着一个口袋掏出口袋里的地址条决定是不是要改写它。一次只能照到一个口袋所以你必须先想好下一个要照哪个口袋再决定改不改当前这个。先照哪个、后照哪个、改完地址条之后手电筒往哪移这三件事想清楚了代码基本不会写错。我自己的习惯是在写任何链表题之前先在脑子里过一遍三张清单第一最终要返回哪个节点是原头、新头、还是某个中间节点第二哪些指针在移动、移动的顺序是什么第三循环退出之后最后一个悬空的指针该怎么处理这三张清单过完再复杂的链表题我也敢动笔。2. 第一道单链表逆序三根指针如何接力题目非常经典输入1 - 2 - 3 - 4 - None要求输出4 - 3 - 2 - 1 - None。也就是说每个节点的 next 要从指向下一个改为指向上一个。这道题之所以是链表入门第一题是因为它把链表最核心的操作——指针重连——体现得淋漓尽致。很多人第一次做这道题时脑子里想的是把链表存到数组再反过来这确实能过但完全没有利用链表的特性。面试官想看到的是你在 O(1) 的额外空间内完成原地反转。2.1 迭代法三根指针接力反转核心思路一句话遍历链表把每个节点的 next 指向前一个节点。但问题来了——链表是单向的当你把当前节点的 next 指向它的前一个节点后当前节点原来的下一个节点就找不到了。所以你需要一个额外的指针在当前节点被修改之前先把它的下一个节点存起来。于是就有了三根指针prev当前节点的前一个节点也就是反转后当前节点应该指向的位置curr当前正在处理的节点next_node当前节点的下一个节点用来防止断链每次循环只做四件事先保存next_node再把curr.next指向prev然后把prev移到当前节点最后让curr走到next_node。这四件事的顺序一步都不能乱。我用一张表把这四轮循环的状态变化列出来初始链表是1 - 2 - 3 - 4 - None循环轮次操作前 currnext_node 保存值执行 curr.next prevprev 更新curr 更新第1轮121.next None12第2轮232.next 123第3轮343.next 234第4轮4None4.next 34None循环结束后curr变成了 None说明已经走到链表末尾而prev停在了原来的尾节点 4 上也就是反转后的新头节点。所以函数最后返回prev而不是返回head。这一步最容易漏很多人写完循环习惯性地返回head结果发现输出还是一大串没变。记住原来的头节点反转后变成了尾节点它的 next 已经是 None 了。代码实现def reverse_list(head): prev None curr head while curr: next_node curr.next curr.next prev prev curr curr next_node return prev时间复杂度 O(n)空间复杂度 O(1)。这个空间复杂度的优势是递归方案比不了的。2.2 递归法处理子链之后再做连接递归的写法比迭代短但理解难度更高。它的思路是假设我能先把当前节点之后的整条子链反转好那我当前节点要做什么假设链表是1 - 2 - 3 - 4 - None递归到节点 2 时如果我让reverse_list(2.next)已经返回了反转后的链4 - 3 - 2这里的 2 是子链的尾那么对于当前节点 1 来说它的下一个节点是 2我需要让 2 的 next 指向我同时把 1 的 next 置空。也就是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代码里的head.next.next head是理解这道题的关键意思是让当前节点的下一个节点反过来指向当前节点。这一步完成之后当前节点原来的 next 指针就已经没有意义了所以下一步想把它的 next 置空。为什么必须置空因为如果不这么做节点 1 和节点 2 会互相指向对方形成一个环最终导致遍历死循环。递归方案的时间复杂度同样是 O(n)但空间复杂度是 O(n)因为递归调用栈会占额外空间。链表足够长时可能会有栈溢出风险。面试时两种方案怎么选我的建议是优先写迭代因为它更稳、空间更优如果面试官问你有没有更优雅的写法可以补充递归。但你得保证自己真的理解递归再展示否则被追问两句就露馅了。2.3 从这道题长出来的高频变体单链表逆序是很多难题的地基。面试中常见的变体包括反转链表前 k 个节点思路和三指针完全一样只不过只执行 k 轮最后要把反转后的链尾接到剩余链上。反转区间 [left, right]先走到 left 前面一个节点把它当作哨兵然后再套三指针反转最后拼接。这个题在 LeetCode 上是 92 号。K 个一组反转链表这是 25 号题。思路是把链表拆成若干组每组做一次区间反转组与组之间再拼接。这时候虚拟头节点就派上用场了后面第三道题会详细讲。这三类变体的本质都是先定位、再反转、后拼接三步走。你把基础逆序吃透了变体只是多几步定位和拼接的细节。写这道题时最常见的错有两个第一next_node没有先保存就去改了curr.next直接导致下一个节点失联第二递归版本里漏写了head.next None结果链表最后两个节点互相指向输出时直接死循环。这两个错我在面试时见过太多次别在它们身上栽跟头。3. 第二道成环检测快慢指针的底气从哪来题目描述很简洁给定一个链表头判断链表中是否存在环。环在链表里表现为某个节点的 next 又指回了它之前的某个节点于是遍历永远走不到 None。这道题的朴素解法是哈希表把一个遍历过的节点存进集合每次遇到新节点先判断它是否已经在集合里。如果在说明成环了。这个方案思路直白代码也好写def has_cycle_hash(head): seen set() curr head while curr: if curr in seen: return True seen.add(curr) curr curr.next return False时间复杂度 O(n)但空间复杂度也是 O(n)。面试时你把这个方案讲出来至少证明你不是一无所知。但面试官大概率会追问能不能把空间复杂度压到 O(1)这时候就要上快慢指针了。3.1 快慢指针为什么能追上快慢指针的方案是慢指针每次走一步快指针每次走两步初始都从头出发。如果链表没有环快指针会先走到 None循环结束如果链表有环快慢指针最终一定会在环内相遇。这里有一个关键问题为什么快慢指针一定会相遇很多人只是记住了结论却没想明白原理。我换个说法解释你就懂了这是一个追及问题。假设链表有环慢指针进入环的那一刻快指针可能已经在环里转了好几圈了。从那一刻开始两个指针都在环内移动。每一轮移动慢指针前进 1 步快指针前进 2 步所以快指针相对慢指针每轮靠近 1 步。环的长度是有限的快指针一圈一圈地追最终必然和慢指针相遇。那为什么快指针每次走 2 步而不是走 3 步、4 步因为相对速度为 1是最安全的。如果快指针每次走 3 步慢指针走 1 步相对速度是 2虽然大概率也能追上但存在跨过慢指针所在节点的可能尤其在环很短的时候反而不如相对速度为 1 来得直观、稳妥。选 2 步是兼顾效率和可理解性的最优解。代码实现def has_cycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False注意循环条件while fast and fast.next。为什么两个都要判断因为快指针每次走两步第一步可能遇到 Nonefast 本身为空第二步也可能遇到 Nonefast.next 为空。漏掉任何一个判断都可能触发空指针访问。写这道题容易出错的另一个点是很多人会把判断写成if slow fast这在 Python 里问题不大因为节点对象比较的是引用但放到某些语言或某些覆写过相等运算的类上可能会变成值比较造成误判。稳妥起见用is来比较身份比较安全。3.2 进阶不仅要判断有没有环还要找到环的入口面试官很喜欢在这个题上追加一问如果链表有环找到环的入口节点。这个问题的标准解法是在第一次相遇之后做一次数学推导。设链表头到环入口的距离为 a从环入口到快慢指针相遇点的距离为 b环的长度为 L。慢指针走过的路程是a b快指针走过的路程是a b nL其中 n 是快指针在相遇前已经在环里多走了的整圈数。因为快指针速度是慢指针的两倍所以有a b nL 2(a b)整理得a nL - b这个式子的含义是从相遇点走 a 步恰好能回到环入口而从链表头走 a 步也恰好到达环入口。所以解法就出来了——把慢指针重置到链表头快指针留在相遇点然后两个指针每次都走一步它们再次相遇的位置就是环入口。def detect_cycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: break else: return None slow head while slow is not fast: slow slow.next fast fast.next return slow这里有个容易忽略的点上面代码里用了while ... else结构。当循环因为fast or fast.next为空而正常结束说明链表没有环不会执行break于是进入 else 分支返回 None。如果有环触发了breakelse 分支就不会执行继续往下找入口。这个写法很简洁没有环和有环但继续处理两种逻辑分得很清楚。3.3 成环检测的思想迁移快慢指针不是只用来判环的。快慢差异这个思路能解决一大类链表问题找到链表的中间节点快指针走完时慢指针正好在中间。找到链表的倒数第 k 个节点让快指针先走 k 步然后两个指针同步走快指针到末尾时慢指针就是答案。判断两个链表是否相交一种做法是先算出两链长度差让长链先走多出的部分再同步遍历找交点也可以把其中一个链表的尾接到另一个链表头上再用成环检测找入口。所以说快慢指针这道题教会你的不只是如何判环而是在链表上制造速度差让问题变成追赶问题的思维模型。这种迁移能力恰恰是算法面试真正想考察的东西。4. 第三道合并两个有序链表虚拟头节点是真香题目描述给定两个升序链表l1和l2把它们合并成一个新的升序链表并返回。比如1 - 2 - 4和1 - 3 - 4合并结果是1 - 1 - 2 - 3 - 4 - 4。这道题的朴素思路是新建一个头节点然后用指针依次比较两个链表的头节点谁小就接谁。但问题是新链表的第一个节点从哪来如果不做任何处理就得先比较一次手动确定哪个节点当新头然后才能进入循环。这样代码会多出一个重复的比较分支而且容易出错。虚拟头节点dummy node就是专门解决这个问题的。4.1 虚拟头节点解决了什么问题所谓虚拟头节点就是先 new 一个额外的节点它本身的数据不参与合并只是为了让整个链表有了一个确定存在的起点。我们的合并指针从 dummy 出发每轮把较小节点接到 dummy 后面。等循环结束真正需要返回的是dummy.next而不是dummy。为什么这个小技巧这么重要因为它把第一个节点需要特殊处理的问题变成了所有节点统一处理的问题。写过链表题的人都知道分支处理越少出错的概率越低。尤其在插入、分区、排序这些需要不断把新节点串到结果链上的场景虚拟头节点几乎是标配。换一个角度理解虚拟头节点就是给空的结果链一个抓手。没有这个抓手你每插入一个节点都要先问一句我插的是第一个吗有了它你只需要无脑向后挂节点最后把多余的空头丢掉。4.2 迭代实现与指针推进细节迭代方案里我们用两个指针l1、l2分别遍历两条输入链用cur指向合并结果链的尾部。每次从中选出值较小的节点接到cur.next上然后移动对应链的指针和cur。def merge_two_lists(l1, l2): dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next if l1: cur.next l1 else: cur.next l2 return dummy.next这里有两个容易忽略的细节。第一个每次接上节点之后cur必须向后移动一位。这个cur cur.next太容易漏了漏掉之后你会发现每次都在覆盖 dummy 后面的同一个位置结果链永远只有最后一个节点。第二个循环结束之后有一个链还没遍历完这时直接把剩余链挂到cur.next上即可因为剩余部分本身已经是有序的不需要再逐节点比较。还有一个很多人会纠结的点为什么是cur.next l1而不是新建一个节点然后复制值因为链表的优势就在于可以复用原有节点直接改指针就能完成合并完全没有必要重建节点。重建节点会增加时间和空间开销在面试中也不是好的信号。4.3 递归实现把选择交给下一层这道题的递归版本非常优雅我自己非常喜欢def merge_two_lists(l1, l2): if not l1: return l2 if not l2: return l1 if l1.val l2.val: l1.next merge_two_lists(l1.next, l2) return l1 else: l2.next merge_two_lists(l1, l2.next) return l2递归的核心逻辑可以理解为每一步只做一次比较。比较l1.val和l2.val把较小的节点作为合并后的头然后让这个节点的 next 指向剩余两个链表合并的结果。因为剩余部分的合并仍然是同一个问题规模更小所以递归可以顺畅地一直走到某个链表为空为止。递归写法的时间复杂度还是 O(mn)但空间复杂度是 O(mn)因为递归栈需要保存中间状态。所以如果面试环境对空间有严格要求迭代方案更稳妥。关于虚拟头节点的迁移我再多说一句。合并 k 个有序链表这道题最朴素的做法是每次从 k 个头节点中选最小的一个节点一个节点往下接更优的做法是分治合并两个两个合再或者用优先队列不断推出当前最小节点。无论哪种做法合并结果链都需要一个虚拟头节点来兜底。你会发现dummy 这个技巧一旦用熟了几乎所有把分散节点重新串起来的题都会自然想到它。5. 三道题之外的调试心得与题型延伸刷链表题和刷数组题有个很不一样的地方数组题出错了你把数组打出来看一眼就能定位问题链表题出错很多时候你盯着代码半天也看不出哪里断了链。所以我想在这个部分分享一些自己的实战调试经验以及这三道题对应思想还能迁移到哪些题上。5.1 两个必写的辅助函数生成链表和打印链表我每次刷链表题都会先写好两个小工具。第一个是把数组转成链表这样我可以很方便地构造测试用例def to_list(arr): dummy ListNode(0) cur dummy for v in arr: cur.next ListNode(v) cur cur.next return dummy.next第二个是把链表打印出来。注意这里有个坑如果你直接把 head 传进打印函数打印完 head 就被移到 None 了后面真正的操作就失效了。所以打印函数内部要用一个临时变量遍历def show(head): res [] cur head while cur: res.append(str(cur.val)) cur cur.next print( - .join(res))有了这两个函数验证反转、合并结果就特别快。比如写完成环检测你可以手动构造一个带环的链表看看函数返回 True 还是 False写完合并把两个数组转成链表后合并再打印出来比对。5.2 链表题的通用调试三板斧第一板斧是画图。链表题光靠脑子想指针稍微多点就绕进去了。把每个节点画成方框、next 画成箭头每一步代码执行完在图上手动移动一次指针。这个过程在做逆序题时尤其有效三根指针在纸上移动两轮整个逻辑就清楚了。第二板斧是拆步骤。链表操作里最经典的错误是先修改再保存导致丢节点。我的习惯是凡是遇到需要同时操作三个及以上指针的场景先在注释里列出步骤顺序再写代码1. 保存 next_node 2. 修改 curr.next 指向 prev 3. prev 移到 curr 4. curr 移到 next_node写注释不丢人丢链才丢人。等你熟练了注释再删掉也不迟。第三板斧是测边界。空链表、单节点、两个节点、尾部插入、尾部删除这五个边界条件是链表题的标配测试。不要以为代码能在标准用例上跑通就结束了很多时候题目里最隐蔽的 bug 恰恰是空链表和单节点场景触发出来的。5.3 同一种思维模型的高频题扩展三道题对应的思维模型分别是指针重连、双指针运动、虚拟头节点。它们能覆盖的高频题比你想象中多得多。关于指针重连最典型的是两两交换链表中的节点和 K 个一组反转链表本质都是先保存、再改指针、后移动。你把单链表逆序写得滚瓜烂熟这些问题就已经解了一半。关于双指针运动链表的中间节点、倒数第 k 个节点、判断链表相交都是同一套思路。这类题的关键在于设计好两个指针的初始位置和移动速度差而不是死记代码。关于虚拟头节点除了合并两个有序链表链表分区、链表插入排序也经常用。它最大的价值是让第一个节点要不要特殊处理这种问题直接消失——按统一逻辑处理完最后返回dummy.next就好。5.4 语言差异C/C 与 Python/Java 的注意点不同语言在链表题上的关注点差别其实挺大的。C/C 里最需要注意指针的指针这个用法比如在链表插入函数里如果要在原头节点前插入新节点只传head过去是改不动的必须传head。另外 C 系语言里节点需要手动分配和释放内存不过做题时一般不用管释放重点看逻辑对不对就行。Python 和 Java 这类带引用类型语言常见的坑是引用别名。比如你写tmp headtmp 和 head 指向同一块内存你通过 tmp 修改了 nexthead 的 next 也会变。这个特性用好了很方便但没想清楚时也容易出问题。尤其是在合并链表这种场景里一个节点既然已经被接进了结果链就不能再用它作为候选去操作了否则结果链会出现意想不到的循环或重复。我自己的体感是链表题练的其实是状态管理能力。它不像数组题那样有一个标准索引供你返回去查看所有操作都发生在一条单向的路上你不能回头只能通过有限几个指针把状态牢牢捏住。一旦你习惯了这种小心翼翼控制状态的写法很多并发、操作系统层面的指针相关概念也会好理解很多。最后再分享一个小经验。我面试别人的时候其实从来不会出难题、怪题基本都是这两三道基础题换着问。能把这简单题写得工整清晰的候选人通常代码能力都不差反过来一上来就背模板、说不出指针为什么这样移动的人多半是死记硬背刷题刷出来的碰到没见过的场景就容易懵。所以不要嫌弃这三道题简单把它们的每一步都吃透比浮光掠影刷五十道难题有价值得多。