链表指针操作核心题组：翻转、旋转与删除重复节点全复盘

刷题这件事很多人习惯按专题推进。最近我把在线判题平台上高频出现的第25题、第61题、第82题放在一起重新过了一遍发现它们非常适合组成一个“链表指针操作”的题组一道是分组翻转里的指针接力一道是旋转时的断链重连一道是重复节点删除时的前驱保护。三题看起来各不相同实际上考的是同一套基本功——对 next 指针赋值时机、节点区间边界、以及“翻转/删除之后前置指针该移到哪”的掌控。这篇文章就把这三道题的核心知识点、代码模板以及我实战中踩过的坑一并写出来适合正在刷链表面试题、准备算法面试或者单纯想把链表指针弄明白的你。1. 为什么把25、61、82组成一个题组链表指针操作的三类考点1.1 三道题的共同底盘next指针的赋值顺序链表题一旦做多了就会明白一个真相算法本身往往不复杂复杂的是“在若干个 next 赋值之间保证不丢节点”。第25题要翻转一整段子链表第61题要把尾部搬到头部第82题要跨过整段重复节点它们本质上都在做同一件事——在合适的时机修改 next并且让不该丢的节点始终被某个指针拽住。很多初学者要么在翻转时把链表弄成环要么在删除时把重复节点漏删一个要么在旋转时算错断开位置。这些问题最后都能归结为一个更底层的原因赋值顺序错了或者中间指针不够用。所以刷这三道题之前先把一个习惯刻进脑子里——每次修改 next 之前问自己一句这个节点被我断开之后还有没有别的指针能帮我找到它1.2 虚拟头节点dummy让头节点特判直接消失这三道题有两道不写 dummy 会非常痛苦有一道没 dummy 基本写不干净。虚拟头节点的作用不是炫技而是把“头节点可能被删除、可能被翻转、可能被移动”这些边界情况吸收掉让代码只在普通节点上做统一操作。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next以第82题为例如果链表是 1-1-2头节点本身是重复节点没有 dummy 的话你得单独写“新头在哪”的判断烦且容易错。加上 dummy 之后头节点的处理逻辑和中间节点完全一致pre 指针永远有一个“前任”判断起来非常顺。我的建议是凡是涉及“头节点可能变化”的链表题一律在开头挂一个 dummy不会有性能损失代码清晰度却能上一个台阶。1.3 刷题前先约定什么是“区间边界”第25题的难点之一是“翻转区间 [start, end]”第61题的难点之一是“找到断开位置”第82题的难点之一是“跳过重复区间”。这三个表述里的共同词是“区间”。链表的区间和数组区间不一样数组有下标链表只有指针所以必须明确我当前说的“区间”是左闭右闭还是左闭右开还是说干脆用“某个指针站在区间前一个节点”的方式来描述。我在解题时偏爱“站在区间前一个节点”的表述。比如说第25题里 pre 永远指向当前待处理组的前一个节点第82题里 pre 指向已确定无重复的最后一个节点。这样做的好处是翻转或者删除之后pre 能立刻通过 pre.next 拿到新的区间头代码逻辑串得特别顺。如果你习惯直接站在区间内也可以但赋值时会多好几处特判。用自己的话把区间边界定义清楚比背模板重要得多。2. 第25题 K个一组翻转链表指针接力与组内翻转拆解2.1 题目回顾与第一反应题目要求给你一个链表每 K 个节点一组进行翻转最后一组如果不是 K 个就不翻转。比如 1-2-3-4-5K2结果是 2-1-4-3-5K3结果是 3-2-1-4-5。很多人第一反应是这不就是循环里调用“翻转子链表”吗。思路方向对但实际操作时两个问题立刻浮出来第一怎么保证翻转完后子链表能正确接回原链表第二怎么判断“剩余节点不够 K 个”。这两点恰恰是这道题的目的。子链表翻转本身不难难的是翻转完之后pre、start、end、nextGroup 这四个指针各就各位让下一轮循环还能继续跑。2.2 标准解法pre、start、end、nextGroup四指针我习惯用的写法是四个指针配合dummy结果链表的哨兵节点。pre当前待翻转组的前一个节点初始指向 dummy。start当前组的头节点初始是 pre.next。end当前组的尾节点需要通过走 K-1 步找到。nextGroup当前组后面那一组的头节点即 end.next。整体流程是先用 pre 往后探测 K 步看剩不剩下 K 个节点。如果探不到第 K 个直接返回 dummy.next如果能探到说明 end 找到了于是记录 nextGroup把 [start, end] 从原链表上“摘下来”翻转再接回去。接回时 pre.next 指向翻转后的头start.next 指向 nextGroup最后把 pre 更新成 start因为翻转后 start 变成了这一组的尾部同时也是下一组的前一个节点。这个流程里最值得体会的是 pre 的更新时机。很多人在翻转完一组之后把 pre 原地不动下一轮就全乱了。pre 必须移动到当前组的“新尾”也就是原来的 start才能让下一轮的探测从正确的位置出发。2.3 翻转子链表时的两个细节第一个细节翻转子链表前要不要把 end.next 置为空可以置空也可以不置空。置空的写法是先把子链表尾部断开然后用常规的三指针迭代翻转。不置空的写法是翻转循环的终止条件写成“当前指针不等于 nextGroup”这样即使子链表后面还挂着节点也没关系反正翻转只在这段区间内进行。我在代码里选择了后一种写法因为少一行赋值而且不容易因为忘记恢复 next 而出错。第二个细节为什么要用 dummy。没有 dummy 的时候链表头作为第一组的 start翻转完以后整个链表的头节点会变你得写额外的代码去更新真正的头。有了 dummy一切都被 pre 这个指针统一管理最后只需要返回 dummy.next。现在刷题环境基本都要求函数返回新的头节点dummy 几乎是这类问题的标准配置。2.4 完整代码与复杂度def reverseKGroup(head: ListNode, k: int) - ListNode: def reverse_list(start, end_next): prev None cur start while cur and cur ! end_next: nxt cur.next cur.next prev prev cur cur nxt return prev dummy ListNode(0) dummy.next head pre dummy while True: # 探测当前组是否还够 k 个节点 end pre for _ in range(k): end end.next if not end: return dummy.next start pre.next next_group end.next # 翻转 [start, end]翻转后返回新的组头 new_head reverse_list(start, next_group) # 接回原链表 pre.next new_head start.next next_group # pre 移动到当前组的尾部也就是原来的 start pre start时间上每个节点只会被遍历常数次总体 O(n)空间上只用了几个指针O(1)。如果你把 reverse_list 写成递归空间会变成 O(k)面试时最好主动改成迭代版本因为很多面试官确实会追问“递归的隐式栈算不算额外空间”。严格来说递归栈算 O(k) 空间k 很小时问题不大但 k 可能等于链表长度最坏 O(n)这点要能答上来。2.5 这道题最常见的翻车现场我见过最多的错误有三个。第一个翻转完忘了把 start.next 接到 nextGroup导致后半段链表直接丢失。第二个反转函数写反了终止条件把整个链表翻转了。第三个pre 更新成 end 而不是 start下一轮探测的起点就错到不知哪里去了。还有一个隐蔽的问题当链表长度恰好是 K 的倍数比如 1-2-3K3反转完是 3-2-1此时循环继续探测end 会探到 None函数返回 dummy.next 正好是 3。这个情况如果在本地测试没跑很容易以为自己写错了其实是正确行为。建议刷完代码后把“长度整除 K”和“长度不整除 K”两种情况各手推一遍印象会深很多。3. 第61题 旋转链表取模、快慢指针与断链重连3.1 题目回顾与“右移k位”的本质第61题的描述给定链表头节点和一个整数 k把链表的每个节点向右移动 k 个位置。比如 1-2-3-4-5k2结果是 4-5-1-2-3。如果你做过数组旋转很容易联想到“把最后 k 个搬到最前面”。但链表没有下标不能直接切片所以这题的核心是找到新的头和新的尾然后改两条 next。本质上旋转就是一次“断链重连”。我们只需要确定两件事第一新的头是原链表的第几个节点第二断开后前后两段怎么接。只要这两个确定了代码只是照做。3.2 第一步求链表长度并取模k 可以比链表长度大很多比如链表长 3k10实际每个节点右移 10 位和右移 1 位效果一样因为 10 % 3 1。所以第一步永远是求出链表长度 n然后执行 k % n。这里有个非常容易踩的坑很多人求出长度之后直接开始移动忘了取模结果 k 很大时整个程序变慢或者因为多移动了整整一圈而恰好没报错掩盖了问题。取模之后如果 k 0说明移动了整数圈链表不变直接返回原 head。这个提前返回不是优化而是防止后面成环操作时算出一个空环。3.3 解法A先成环再断开解法A的思路是先遍历一遍找到尾节点顺便得到链表长度 n。然后把尾节点的 next 指向 head让链表变成一个环。接着从 head 开始走 n - k 步等等这里的“从 head 开始走几步”是最容易懵的地方。我理一下推导过程。旋转后新的头是原链表倒数第 k 个节点也就是正数第 n-k1 个节点从 1 数起。那么新尾就是正数第 n-k 个节点新尾的 next 要设为 None。好我们需要找到这个节点。它距离 head 正好 n-k-1 步。用一个指针从 head 走 n-k-1 步就到了新尾新尾.next 就是新头然后把新尾.next 置空即可。def rotateRight(head: ListNode, k: int) - ListNode: if not head or not head.next or k 0: return head # 求长度并让尾节点指向头节点形成环 n 1 tail head while tail.next: tail tail.next n 1 k % n if k 0: return head tail.next head # 新尾正数第 n-k 个节点 steps n - k - 1 new_tail head for _ in range(steps): new_tail new_tail.next new_head new_tail.next new_tail.next None return new_head这个解法最大的记忆点在于“先成环再找断点”。成环让“把尾部接到头部”这个动作天然完成后面只需要一次性断开。理解之后非常优雅代码量也小。3.4 解法B快慢指针解法B不需要成环用快慢指针定位。快指针先走 k 步然后快慢指针一起走直到快指针到达尾节点。此时慢指针停在倒数第 k1 个节点也就是新尾。具体来说快指针和慢指针之间始终隔着 k 个节点。快指针到最后一个节点时慢指针正好指向倒数第 k1 个节点。def rotateRight(head: ListNode, k: int) - ListNode: if not head or not head.next or k 0: return head n 1 tail head while tail.next: tail tail.next n 1 k % n if k 0: return head fast slow head for _ in range(k): fast fast.next while fast.next: fast fast.next slow slow.next new_head slow.next slow.next None fast.next head return new_head对照一下两个版本成环法利用一个环把首尾连接快慢指针法在最后一步手动 fast.next head。成环法更省心但要注意别忘记断开快慢指针法直观一些适合跟面试官讲“我要找倒数第 k1 个节点”的经典应用。两种都要会写面试时看哪套思路更顺口就先讲哪套。3.5 边界情况与实测注意点这道题的边界情况相当多。空链表、单节点链表、k0、k 是链表长度的整数倍、链表长度为 1 时 k 很大这些情况里最简单的处理是在函数开头加一个统一判断if not head or not head.next or k 0: return head。这里 k 还没取模所以 k 0 的判断必须在取模前后都有因为原始 k 就可能为 0。我见过有人把取模之后 k0 的提前返回漏掉然后成环法里 steps n-k-1 n-0-1 n-1让 new_tail 从 head 走 n-1 步正好走到原来的尾节点然后 new_head tail.next也就是原来的 head再 new_tail.nextNone结果链表被从中间砍断只剩头和尾不对实际上这样会把链表断成两段整段数据丢失一半。总之k0 的提前返回不是为了“快”是为了“不错”。4. 第82题 删除重复元素II前驱指针的“退一步”检查逻辑4.1 题目回顾和“保留一个”版本的区别第82题要求在一个已排序的链表中删除所有有重复数字的节点只保留原始链表中没有重复出现的数字。这句话最容易被理解成“每种数字保留一个”——那其实是另一个版本的题它只需要删掉多余的重复项让每个数字只出现一次。第82题更狠只要某个数字出现了多次这个数字的所有节点全部删掉一个不留。举个例子1-2-3-3-4-4-5结果是 1-2-5。注意 3 和 4 都从链表里完全消失了。如果只做“保留一个”版本结果是 1-2-3-4-5。必须先把这个区别吃透不然后面的指针逻辑根本对不上。既然题目已排序说明重复节点一定相邻这给“跳过一整段重复区间”提供了可能。4.2 核心思路pre不急着向前走这道题的标准思路是用 pre 记录“已确定无重复”的最后一个节点再用 cur 从 pre.next 开始检查。检查时会遇到两种情况cur.next 存在且 cur.val cur.next.val说明 cur 所在的数字是重复的。此时不知道这串重复节点在哪结束所以用内层循环一路走到最后一个重复节点然后 pre.next cur.next把整段重复节点全部跳过。跳过之后pre 不要立刻移动因为 pre.next 指向的新节点也可能有重复必须留在原地再检查一轮。另一种情况是 cur 的值不重复才把 pre 移到 cur。这个“pre 不急着走”的逻辑是全题的核心也是很多人卡壳的地方。很多人的第一反应是发现重复之后把 pre 往后挪结果一挪就把 pre.next 指到了重复段内部后面的处理全乱。正确的心法是pre 是安全区和非安全区的分界线只要 pre.next 指向的节点还没被确认安全pre 就不能动。4.3 完整代码两种写法 复杂度def deleteDuplicates(head: ListNode) - ListNode: dummy ListNode(0, head) pre dummy while pre.next: cur pre.next if cur.next and cur.val cur.next.val: # 找到重复段的最后一个节点 while cur.next and cur.val cur.next.val: cur cur.next # 跳过全部重复节点 pre.next cur.next else: pre pre.next return dummy.next另一种写法是拿 cur 和 pre 两个指针自己管理移动效果等价但代码会稍微长一点。我更推荐上面的写法因为它把“pre 暂不移位”这个逻辑直接体现在结构里只要当前段被判定为重复pre 就不进 else 分支自然原地等待下一轮。时间复杂度 O(n)每个节点至多被访问常数次空间 O(1)。这题用递归也可以但递归栈会让空间变成 O(n)面试时优先给出迭代版本最稳妥。4.4 最容易写错的地方第一个高频错误是没处理头节点重复的情况。比如 1-1-2 这样的输入如果没有 dummy头节点就是重复节点你得额外想想新头是什么。有 dummy 后pre.next 一开始就指向那个重复节点循环直接进入“跳过”分支pre.next cur.next也就是跳到 2头节点自然就更新了完全不需要特判。第二个高频错误是内层循环的边界条件写错。比如写成 while cur.val cur.next.val但没有先确认 cur.next 非空最后会报空指针异常。注意外层循环判断的是 pre.next内层循环判断的是 cur.next两层各管各的不能混。第三个高频错误是把“删除重复元素”理解成了“保留一个”写完代码跑在 1-1-1 上返回 1但正确结果是空链表。我自己刷这题时就栽过第一次还是因为读题不仔细。建议刷题之前把题目里“全部删除”和“保留一个”这两个关键表述圈出来避免在思路起点就偏了。5. 三道题的横向复盘易错点对照与面试追问思路5.1 三题核心考点一张表三题放在一起复盘的时候我习惯先拉一张表把每道题的核心操作、关键指针、最值得警惕的边界都列出来边写边回忆自己的踩坑过程。题号核心操作关键指针最需要警惕的边界第25题每K个一组翻转子链表pre / start / end / nextGroup剩余不足K个长度恰好是K的倍数第61题整体右移K位断链重连fast / slow 或 tail / headK过大取模K为0旋转后新尾定位第82题删除所有重复数字的所有节点pre / cur头节点重复整条链表全部重复pre不移动这张表的作用是帮助快速定位解题思路。遇到任意一道链表题先问自己三个问题会不会新建 dummy会不会出现长度或步数和实际节点数不一致pre 或者某个指针该不该移动这三个问题回答清楚代码基本就出来了。5.2 常见错误排名与规避方法我把读者高频报错归纳成四类并给出排查建议空指针异常通常是没有先判断 cur.next 或者 head 为空。写循环条件时凡是访问 next 的属性都先在前面加 not 判断顺序写对。链表断成两截翻转或删除后忘记接回剩余部分。对策是每次修改 next 之前先用一个临时指针保存后面节点。代码写完后从函数返回的头节点沿着 next 走一遍确认没有节点丢失。死循环或成环翻转时把尾部接回了前面或者 61 题成环后忘了断开。对策是在本地测试里加一个“走 N 步看是否绕回”的检查或者直接检查代码中是否存在一个节点的 next 指向了自己或前序节点。边界理解成理想情况比如 25 题忘记不足 K 个不翻转82 题忘记全部重复返回空。对策是把边界输入写在笔记开头每次写完顺手测一遍。5.3 面试中的追问和变体面试官很喜欢拿这三题做发起点延伸出一串问题。第25题最常见的是“K2 时你是怎么做的”其实那就是另一道经典题两两交换节点。如果你能顺口说出“K2 只是这个答案的特例递归和迭代都能写”会是一个不错的加分点。第61题常见变体是“如果只允许 O(1) 额外空间你能写吗”此时成环法正好满足要求。第82题常见追问是“如果链表没有排序你怎么做”那往往需要换用哈希表先统计频率空间复杂度会升到 O(n)这也是值得准备好的对比方案。另外三道题都能引出“递归 vs 迭代”的讨论。第25题递归写法会让翻转子链表的代码更短但隐式栈空间算不算额外空间这个问题最好提前想清楚。第61题递归写旋转很别扭几乎不用第82题递归写删除也不自然。所以我的建议是把迭代版本练成肌肉记忆递归作为备选方案讲给面试官听即可。5.4 二刷建议与自测清单如果你把这篇文章当作复习笔记二刷的时候可以试一个“不看题解默写”的方法给自己 15 分钟只凭记忆写三题的完整代码然后对着下面这个清单自查。第25题链表长度不足 K 时返回原链表长度等于 K 时整个链表翻转翻转后的 tail 有没有正确连上后续节点。第61题k0 时返回原链表k 大于链表长度时先取模单节点链表不能成环后死循环。第82题输入 1-1-1 时返回 None输入 1-1-2-2-3 时返回 3输入完全没有重复时pre 一路向后移动结果和原链表一致。如果你能一次通过这四个清单这套题组基本就吃透了。最后分享一个我自己的小习惯每写好一道链表题不急着提交判题先手动构造三组输入分别覆盖“空链表或单节点”“头节点会变化”“长度和K/重复段边界纠缠”的情况然后拿笔在纸上画一遍指针移动。虽然看起来多花五分钟但这五分钟省下的调试时间往往是半小时。链表题最怕的就是眼睛看懂了手却不知道把指针放哪画图是解决这个问题最笨也最有效的方法。