链表操作是数据结构与算法里最“动手”的一类题目移除链表元素、设计链表、翻转链表、两两交换链表中的结点、删除链表的倒数第n个结点、环形链表这六个问题几乎把链表的基础技巧覆盖了个遍。我在面试候选人和给自己准备复习时都反复用这套题练手它们真正考察的不是背代码而是对指针移动、边界条件、迭代与递归切换的理解。这篇东西就是想把这几道高频链表题连成一条线讲透适合刚开始刷题的新手也适合已经刷过一些题但总觉得链表不爽的人做减法。1. 内容整体设计与思路拆解1.1 为什么链表操作总是面试场的常客先聊一个很多人困惑的点数组和链表都能存数据为什么面试官偏偏爱考链表因为数组有下标访问和修改都是“随机访问”而链表是“顺序访问”每一步操作都强依赖当前结点的引用。这意味着你在写逻辑时大脑里必须时刻保有一张“结点连接关系图”稍不留神就会丢指针或者形成环。另一个原因是链表能非常干净地暴露一个程序员的基本功你有没有考虑空指针有没有处理头结点和尾结点的特殊位置有没有把循环边界写对这些习惯在工程里同样重要比如操作系统内核里的链表、Redis的链表实现、网络驱动里的环形缓冲全都是同一套思维。所以这六个题不是孤立的考点它们本质上是“指针操作训练营”。1.2 六个题目背后的共性套路把这六道题放在一起看你会发现它们不是在零散地考六个技巧而是反复在考三种套路虚拟头结点、双指针/快慢指针、递归与迭代的相互转换。虚拟头结点移除链表元素、设计链表、删除倒数第n个结点都会用到它。核心思想是让头结点也像一个普通结点一样被处理避免写一堆if head null的特判。双指针删除倒数第n个结点需要快慢指针拉开距离环形链表需要快慢指针检测相遇。这两个题表面不同内部都是“让两个指针以不同速度或不同起点移动”的思想。递归视角翻转链表和两两交换结点都可以用递归写虽然迭代更高效但理解递归版本能帮助你看到问题的结构它无非是把大问题切成小问题然后处理当前层。我在带新人时一直强调先学会识别这些套路再动手写代码。你一眼看出题目该用虚拟头还是双指针效率会高很多。2. 核心细节解析逐个击破六个操作2.1 移除链表元素边界条件与迭代思路题目要求是给定一个链表删除所有值等于目标val的结点。看起来很简单但坑在头结点。如果头结点本身就要被删除直接让head后移即可但链表一旦变长连续多个结点都需要删除时就很容易写乱。最稳妥的做法是创建一个虚拟头结点dummy它的next指向真正的头结点然后从dummy开始遍历不断检查curr.next的值是否等于val。如果相等就把curr.next跳过那个结点curr.next curr.next.next。这里有个细节跳过之后curr不动因为新的curr.next可能仍然需要被删除如果不等curr才向后移动。比如链表1 - 2 - 6 - 3 - 6删除6用虚拟头后流程是dummy(0) - 1 - 2 - 6 - 3 - 6遍历到2时发现2.next是6直接连到3此时curr仍停在2而不是移到3接着检查新的2.next是3才前进。这个“跳过时不移动”的动作是很多人第一次写错的点。还有一种是递归写法head.next removeElements(head.next, val)然后判断head.val是否为val。递归写起来很优雅但实际工程里链表可能很长递归栈会爆用迭代虚拟头更稳妥。2.2 设计链表接口设计与底层存储这道题要求实现一个链表类通常有get(index)、addAtHead(val)、addAtTail(val)、addAtIndex(index, val)、deleteAtIndex(index)这些方法。它不只是考算法还考工程设计。你首先得决定底层是用单链表还是双链表。单链表操作尾部时要先遍历到最后一个结点双链表更灵活但需要维护多一个prev指针代码量直接翻倍。面试时默认单链表就够除非题目明确要求O(1)的尾部操作。这里最核心的是索引边界处理。题目经常会用“如果索引无效则返回-1”或“如果索引无效则不执行任何操作”这类描述。实际实现时我习惯重新定义addAtIndex中如果能插入的位置是[0, size]那么index size时加到尾部index 0时加到头部。为了统一处理还是用虚拟头节点并把连接操作拆成两个方法getNode(index)用来找结点getNode返回的是前驱结点还是目标结点要事先想清楚否则后续删改会错位。我踩过的一个坑是getNode(index)里循环条件写成while(index 0)还是while(index 0)没想明白。真相是如果你拿到的是目标结点循环index次即可如果你需要的是前驱结点循环index次后停在目标前一位。建议直接写getPrev(index)语义更清晰。2.3 翻转链表三指针法与递归法翻转单链表是链表题的“hello world”解法有迭代和递归迭代最常用。你需要三个指针prev初始为nullcurr初始为headnext用来保存curr.next。每轮循环做四件事先把next临时存下来让curr.next指向prev再把prev和curr都前进一步。这里最容易出错的是第三步的顺序必须先保存next否则一旦修改curr.next后面的结点就丢了。很多人第一版代码就挂在这一点上。循环结束时curr为nullprev正好指向新的头结点返回prev即可。注意这是原地翻转空间复杂度O(1)时间复杂度O(n)没有额外创建结点。递归版本则是先翻转剩余链表再把当前结点放到末尾。核心调用是newHead reverseList(head.next)然后head.next.next head最后head.next null。这个head.next.next head真的很难直觉理解我当时是画图画了半小时才转过来。递归的好处是代码短坏处是深链表会栈溢出不推荐在工程里用。2.4 两两交换链表中的结点步骤拆解与指针更新顺序两两交换要求把相邻结点成对互换并且不修改结点值只改动指针。这是所有链表题里“指针更新顺序”最讲究的一题。以dummy - node1 - node2 - next为例目标是变成dummy - node2 - node1 - next。你需要同时操作三个连接dummy.next指向node2node2.next指向node1node1.next指向next。关键是更新顺序先改dummy.next再改node2.next最后改node1.next。如果先改node1.next为next那你可能还没有保存node2的引用导致下一步无法操作。我用一个更稳的写法先把first curr.next再把second curr.next.next然后依次执行curr.next second、second.next first、first.next second.next。这里second.next需要在新连接建立前保存吗其实不需要因为执行到first.next second.next时second.next仍指向原来的后续结点没有被破坏。暂停条件也要小心curr需要在下一组交换前移动到first因为下一组的“前驱”交换后变成了第一结点。我见过很多人把curr移到second结果跳过了一组。2.5 删除链表的倒数第n个结点双指针一次遍历常规思路是两次遍历第一次求长度第二次走到len - n处删除。这样简单但面试官通常会追问“能不能只扫一遍”答案就是快慢指针。让快指针先走n1步这样快指针走到末尾null时慢指针正好停在倒数第n个结点的前驱位置。为什么是n1而不是n因为你需要前驱来删除目标如果让快指针只走n步慢指针会停到目标上删除时就拿不到前驱了。用虚拟头结点避免“删除头结点”这种边界特例。注意一个细节题目里的链表可能正好长度等于n此时删除的是头结点。如果你不用虚拟头head指针需要更新用虚拟头后dummy永远不会被删所以返回dummy.next就好。我自己在实现时还会加一个防御先检查链表长度是否小于n如果小于直接返回原链表。2.6 环形链表快慢指针与数学证明环形链表问题有两个版本判断有没有环以及找环的入口。这里只说判断有环因为找入口可以在这个基础之上展开。核心是 Floyd 判圈算法设置slow每次走一步fast每次走两步。如果链表没有环fast会先碰到null如果有环两个指针一定会在某个时刻相遇。这个结论很多人只背不证明其实证明也不难设链表中无环部分长度为a环长度为b当slow进环时fast已经比slow多走了若干距离因为步长差为1所以经过有限步后fast一定能“追上”slow。还有一个容易忽略的细节fast初始值到底是从head开始还是从head.next开始都可以但循环条件要配套。我习惯写while slow ! fast先把slow和fast都初始化为head然后先移动再判断这样避免一开始就相等导致不进循环。还有一种写法是初始化slow head、fast head.next再把循环判断改成while fast ! null fast.next ! null。这个题要特别注意空链表和一个结点的链表直接返回false。有的实现里忘了判断fast.next会报空指针异常。3. 实操过程与核心环节实现3.1 代码骨架与测试环境写链表题之前我建议先固定一个代码骨架减少重复劳动。以 Python 为例定义结点类和常用辅助函数class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def build_list(arr): dummy ListNode(0) cur dummy for v in arr: cur.next ListNode(v) cur cur.next return dummy.next def print_list(head): res [] while head: res.append(head.val) head head.next print(res)为什么用 Python因为 Python 在力扣里写起来最省心不需要手动管理内存。但如果你在准备 C 面试记得注意delete释放结点——不过刷题时为了简洁可以不用手动释放实际工程才需要。测试时就靠build_list([1,2,3,4,5])构造链表用print_list打印结果比在编辑器里手动创建对象快得多。我建议把这套模板保存在本地刷题时直接粘贴省下的时间都用来思考算法。3.2 六道题的实现与关键注释下面逐一给核心实现我尽量写清楚每一行在干什么。移除链表元素def removeElements(head, val): dummy ListNode(0) dummy.next head cur dummy while cur.next: if cur.next.val val: cur.next cur.next.next else: cur cur.next return dummy.next注意cur.next可能为空所以循环条件是while cur.next不是while cur。如果没有虚拟头删除头结点时要单独处理这就是为什么我强烈建议虚拟头。设计链表的关键部分class MyLinkedList: def __init__(self): self.dummy ListNode(0) self.size 0 def get(self, index): if index 0 or index self.size: return -1 cur self.dummy.next for _ in range(index): cur cur.next return cur.val def addAtIndex(self, index, val): if index 0: index 0 if index self.size: return prev self.dummy for _ in range(index): prev prev.next new_node ListNode(val) new_node.next prev.next prev.next new_node self.size 1这里addAtIndex是核心addAtHead和addAtTail都调用它。我维护一个size字段避免每次都遍历算长度也方便做边界判断。get里返回-1是题目要求其他语言可能要求返回null。翻转链表迭代版def reverseList(head): prev None cur head while cur: next_node cur.next cur.next prev prev cur cur next_node return prev顺序就是“保存后继 - 改指向 - 移动 prev - 移动 cur”。我在代码里把next_node变量名写得很显眼就是为了提醒自己先保存。两两交换def swapPairs(head): dummy ListNode(0) dummy.next head cur dummy while cur.next and cur.next.next: first cur.next second cur.next.next cur.next second first.next second.next second.next first cur first return dummy.next我习惯把first和second命名成“第一个结点”和“第二个结点”然后在纸上画出连接顺序。很多人写反first.next second.next和second.next first的顺序其实只要second还没被修改谁先谁后都行但为了整齐我固定成“先连后面再回头”。删除倒数第 n 个结点def removeNthFromEnd(head, n): dummy ListNode(0) dummy.next head fast dummy slow dummy for _ in range(n 1): fast fast.next while fast: fast fast.next slow slow.next slow.next slow.next.next return dummy.nextfast先走n1步保证slow最终在被删结点的前驱。如果 n 等于链表长度fast走完后正好走到null循环里fast为假不进入循环直接删除头结点这个边界刚好被虚拟头接住了。环形链表def hasCycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False我习惯先移动再比较让slow和fast初始都指向head。有的实现先比较再移动那样的话head如果非空且head.next head就能检测到但那种写法在空链表上要加判断。我这里用while fast and fast.next同时避免了空指针。3.3 复杂度分析与优化思路六个题最标准的复杂度如下移除链表元素时间O(n)空间O(1)因为只遍历一次。设计链表get和addAtIndex最坏O(n)addAtHead是O(1)空间是O(n)。如果要优化尾部操作可以用双链表加尾指针但代码复杂度会上去。翻转链表迭代版时间O(n)空间O(1)递归版空间O(n)。两两交换时间O(n)空间O(1)。删除倒数第 n 个结点快慢指针版本时间O(n)空间O(1)比两次遍历只少了一次循环但对超长链表性能有实质提升。环形链表时间O(n)空间O(1)。很多人面试时会被追问“还能不能优化”记住一个原则链表题里空间复杂度从O(n)降到O(1)通常是通过“原地改指针”时间复杂度从O(n)降到更快是不可能的因为至少要把每个结点扫一遍。所以你要说的优化方向应该是“少扫描几遍”比如删除倒数第 n 个两次遍历变成一次遍历。4. 常见问题与排查技巧实录4.1 空指针与极端输入先写防御再写逻辑链表题最容易崩的就是空指针。我复盘了自己和学员写过的错高频场景有三个一是删除时没有检查cur.next是否为空直接访问cur.next.val二是删除倒数第 n 个时没有处理fast为null的情况三是环形链表里没判断fast.next是否存在导致fast.next.next直接炸。我的应对办法是在写主逻辑之前先想清楚三个空输入场景——空链表、只有一个结点、删除头结点或尾结点。比如移除链表元素时输入[]虚拟头直接返回dummy.next也就是None完全正确输入[7]且val7cur.next会被更新返回None也正确。这种自觉排查能让你的代码在面试里显得老练。4.2 循环条件与指针更新顺序错误循环条件是链表题的第二大雷区。典型错误是删除倒数第 n 个时for循环次数写错导致slow停在目标结点而非前驱。我的调试技巧是用一个短链表手动模拟链表[1,2,3,4,5]n2dummy - 1 - 2 - 3 - 4 - 5fast先走三步到达3然后slow和fast一起走直到fast到null此时slow停在3删除4正好是倒数第二个也就是4。这样手推算比眼睛看代码快得多。两两交换里指针更新顺序更是容易连环错。我总结了一个口诀“先连后面再连前面最后改 order 里的指针”。具体说就是先把当前轮的“第二个结点”接到“后面的结点”再把“第一个结点”接到“第二个结点”的后面最后把前驱接到“第二个结点”。顺序万无一失。4.3 调试技巧与测试用例设计面试或刷题时最常见的调试方式是打印链表但打印出一整串很费眼睛。我更喜欢写一个print_list函数再配合小样例检查每个阶段。比如翻转链表打印每一轮循环后prev和cur的指向你就能快速看出哪一步出了问题。测试用例我通常固定准备这么几条空链表、只有一个结点、两个结点、多个结点并且目标值出现在头尾、目标值连续出现比如[1,1]删除1、删除倒数第一个尾结点、删除倒数第n个正好等于链表长度。这套用例能覆盖绝大多数边界跑完心里就踏实了。关于环形链表我还会特意构造一个只有两个结点且首尾相接的环比如1 - 2 - 1验证fast会不会陷入死循环。实际上因为步长差为 1快慢指针一定会相遇不会死循环但第一次写时总担心它会不会无限跑下去所以这个用例能给自己吃定心丸。5. 实操心得怎么把这些题变成肌肉记忆我个人刷链表题的经验是不要死记代码而是先把六种操作的“指针移动图”画一遍。我在白板上画过无数次prev、curr、next的箭头变化画完之后再写代码速度至少快一倍。画图有个固定方法把每一步之前的红色箭头用虚线表示操作后的新连接用实线表示被断开的旧连接用叉号标记。这样你能一眼看出哪根指针还没更新哪根更新前需要先保存。这个方法在面试时也适用你可以直接跟面试官说“我先画一下指针状态”反而显得沟通能力强。想进阶的话把今天讲的六个题改成“用递归实现翻转和交换”虽然迭代已经能解决但递归能训练逆向思维。我试过把swapPairs改成递归版递归返回的是下一组交换后的头结点然后当前层把自己跟递归结果连起来。做完之后以后看任何链表递归题都会顺很多。最后分享一个小技巧很多题的答案并不仅仅属于方法层面你还可以把“虚拟头结点”和“双指针”这两个技巧抽象成模板遇到新题先套模板。比如看到“删除倒数第 k 个结点”立刻想到快慢指针看到“交换相邻结点”立刻想到虚拟头 三指针。这种条件反射刷题很管用。今天就记这些下回再聊更复杂的链表排序题。