删除链表倒数第N个节点：双指针与哨兵节点详解

带新人刷链表题这几年我发现最容易被低估的题目就是删除链表的倒数第 N 个结点。你说它难吧第一版代码很快就能写对你说它简单吧一旦加上“只遍历一次”的要求很多人会在白板上改三五遍还改不干净。原因在于我们习惯了从头部往尾部数数而“倒数第 N 个”这个概念在单向链表里天然没有直接表达。数组可以靠下标一步定位链表做不到。这道题的最优解是双指针——让一个指针先走出去另一个指针保持固定间距跟在后面用“间距感”在单次遍历里同时完成定位和删除。今天的整理是我刷题系列的第11篇对应原题第19题我会把两遍遍历和双指针两套方案都拆开讲重点放在后者为什么是唯一解、代码怎么写、边界条件怎么一次全过。1. 为什么“倒数第N个”天然是个坑1.1 链表和数组的根本差异没有“反向索引”理解这道题之前得先想清楚链表这个数据结构的脾气。数组是连续存储的arr[len-1-n] 一行代码就能拿到倒数第 n 个元素因为数组支持随机访问下标是天然属性。但单链表只有一个 head 和若干个 next 指针每个节点只知道自己后面的节点是谁不知道自己前面的节点是谁。你没法从末尾往前走也没法直接跳到某个位置所有访问都只能从 head 开始逐个 next。所以“删除倒数第 n 个结点”这句话翻译成人话就是我不知道链表有多长却要直接操作从末尾数的第 n 个位置。这就像你在一列看不到尾的队伍里要求从队尾往前数第三个人出列——你如果不先走到队尾根本不知道第三个人站在哪。这个“信息缺失”才是题目的真正难点。面试官问“能不能只遍历一次”本质就是问能不能在不知道长度的情况下仍然准确定位到这个位置。1.2 两遍遍历能写对但不是最优解多数人第一反应是先数长度再走第二次。思路很直白第一遍从头走到尾得到链表长度 L第二遍从头部走 L-n 步到达目标节点的前驱然后修改指针完成删除。def remove_nth_from_end_v1(head, n): length 0 p head while p: length 1 p p.next dummy ListNode(0, head) p dummy for _ in range(length - n): p p.next p.next p.next.next return dummy.next这段代码是正确的。为什么第二遍要走 length-n 步因为长度为 L 的链表倒数第 n 个节点的正数编号是 L-n1节点从 1 编号它的前驱正数编号是 L-n。从 dummy 出发走 L-n 步恰好落在它的前驱上。但它的代价是两轮遍历时间复杂度虽然也是 O(L)但常数翻倍。更重要的是它完全没有利用链表的结构特性只是把“数组思维”硬套在链表上。面试官追问一句“能不能只走一遍”你就得给出真正的解法。1.3 递归也能“只走一遍”但代价不小还有一种思路是递归。递归到链表末尾回溯的时候计数也能找到倒数第 n 个节点。它确实在物理上只对链表走了一遍但代价是递归深度等于链表长度空间复杂度是 O(L)。长链表下一万层递归就是一万层函数栈轻则慢重则栈溢出。更别说递归隐含的额外内存开销在工程上通常不可接受。所以递归可以作为思路提一嘴但它不是这道题的标准答案——面试官想看到的正是那个不依赖递归、不依赖额外数组的 O(1) 空间解法。2. 双指针用“间距”取代“测长度”2.1 核心思想是制造一个固定窗口双指针解法的思路一句话就能说清让两个指针始终保持 n1 个节点的间距同步前进快指针走到链表末端时慢指针正好停在目标节点的前驱上。为什么是 n1不是 n也不是 n2这里值得认真推导一下很多资料直接甩结论搞得人只能死记硬背。设链表长度为 L。为方便计数把 dummy 节点看成“第 0 个位置”真正链表节点是第 1 到第 L 个位置。删除倒数第 n 个节点它本身的正数编号是 L-n1它的前驱正数编号是 L-n。再看双指针的运动过程。fast 从 dummy 出发走 L1 步一定会碰到 None——因为从 dummy 到末尾一共要跨过 dummy 加上 L 个真节点共 L1 个 next 跳转。假设 fast 先走 k 步然后两个指针同速前进等 fast 走到 None 时slow 从 dummy 出发总共走了 L1-k 步。要让 slow 恰好停在前驱位置就要求L1-k L-n解出来k n1所以 fast 必须先走 n1 步这是一个精确推导不是拍脑袋定的。这个公式特别适合在面试时直接说出来比“快指针先多走一步”这种模糊说法有说服力得多。2.2 慢指针停在“前驱”而不是目标本身很多人第一次写这题会写成 fast 先走 n 步。这样做对不对我们来推一下。如果 fast 先走 n 步fast 碰到 None 时 slow 从 dummy 出发走了 L1-n 步。对照公式slow 的正数编号是 L1-n而目标节点的正数编号是 L-n1两者编号相等——也就是说 slow 恰好停在被删节点本身。问题来了删除一个节点理论上只需要把它的前驱的 next 指向它的后继。如果你手里只有被删节点没有前驱指针你必须额外用一个变量记录上一个访问过的节点或者先保存当前节点再走一步去拿前驱。无论哪种做法代码都会多出分支判断不如让 slow 直接停在前驱位置一条slow.next slow.next.next收工。这就是 fast 先走 n1 步而不是 n 步的原因少一步定位到的是目标本身多一步才是目标的前驱。删除操作要的是前驱。2.3 哨兵节点统一边界逻辑再来看 head 的特殊性。如果被删除的正好是头节点head 没有前驱处理起来就要写出 if 分支单独更新 head。代码一有分支边界就容易漏。解决办法是加一个 dummy 哨兵节点让它指向 head。这样一来核心里没有任何一个节点是“没有前驱的”dummy 就是头节点的前驱。删除任意节点都统一成slow.next slow.next.next最后返回 dummy.next而不是 head。因为 head 可能已经被删掉了dummy.next 才是删除操作后的真正头节点。这个技巧不只在这道题有用。凡是涉及链表头节点可能变化的题目“加一个虚拟头”几乎都是默认操作。它牺牲一个节点占位换来的是代码结构上的统一这笔交易非常划算。3. 完整实现与指针追踪3.1 参考代码Python 版本class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def removeNthFromEnd(head: ListNode, n: int) - ListNode: dummy ListNode(0, head) fast dummy slow dummy # 快指针先走 n1 步确保 slow 最终落在被删节点的前驱 for _ in range(n 1): fast fast.next # 两个指针保持间距同步前进 while fast is not None: fast fast.next slow slow.next # 摘除倒数第 n 个节点 slow.next slow.next.next return dummy.nextC 版本逻辑完全一致ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy(0, head); ListNode* fast dummy; ListNode* slow dummy; for (int i 0; i n; i) { fast fast-next; } while (fast ! nullptr) { fast fast-next; slow slow-next; } slow-next slow-next-next; return dummy.next; }两个版本的结构一模一样先走固定步再同步走最后删除。C 版本唯一要注意的是for (int i 0; i n; i)一定要是写 n或者i n1都对但写成i n就少走了一步slow 最后会停在错误位置。3.2 用一个实例完整跟踪指针位置口头说一百遍不如手动跑一遍。我习惯用一条五节点链表来演示1 → 2 → 3 → 4 → 5假设 n 2也就是删除倒数第 2 个节点值为 4 的节点。dummy 节点的 next 指向 1。整个过程一共有 6 个节点位置dummy 加上 5 个真节点fast 从 dummy 到 None 需要走 6 步。fast 先走 n1 3 步落在节点 3然后两个指针同步走。阶段fast 指向slow 指向说明初始dummydummy两个指针都在虚拟头fast 先走 3 步3dummy间距固定为 3第 1 轮循环41间距保持 3第 2 轮循环52间距保持 3第 3 轮循环None3fast 到底循环终止执行删除None33.next 3.next.next跳过值为 4 的节点最后链表变成 1 → 2 → 3 → 5值为 4 的节点被摘除正确。注意第 3 轮循环结束时slow 指向的是值为 3 的节点它是待删节点 4 的前驱。这时候slow.next slow.next.next把 3 的 next 直接改成 5删除完成。整个过程 fast 只完整走了一遍链表slow 只是跟在后面。3.3 复杂度和“只遍历一次”的严格含义时间复杂度fast 指针从头到尾走过一次slow 指针至多跟进到链表尾部整体是 O(L)L 是链表长度。空间复杂度只用了两个局部指针变量没有额外容器、没有递归栈所以是 O(1)。“只遍历一次”的严格说法是整个算法对链表执行了一次完整的线性扫描没有任何二次回访。快指针先走的那 n1 步是这一次扫描的一部分不额外增加扫描轮次。为什么这样算一次因为 fast 从 dummy 走到 None总共只推进了 L1 次 next之后的每一步都没有重复访问之前已经走过的节点。整个过程是一趟完整的、无重复的线性行程。4. 边界条件实测三个最容易翻车的用例代码写完提交之前先过三关。这是我自己实测时踩出来的经验题目真正挖的坑基本都藏在边界里核心逻辑反而很少出错。4.1 用例一n 等于链表长度需要删除头节点链表 1 → 2 → 3n 3。这时要删除头节点 1。fast 从 dummy 出发走 n1 4 步。走完 4 步之后 fast 正好是 None于是while fast is not None循环体一次都不执行slow 还停在 dummy 上。此时slow.next就是头节点 1执行slow.next slow.next.nextdummy 直接指向原链表的第二个节点 2返回dummy.next得到的正是 2。头节点被正确删除没有任何特殊分支。这组用例特别能检验你对n1步的理解。如果少走一步fast 走 3 步指向节点 3循环体还要跑一轮slow 最后会指向节点 2操作的是节点 2 的 next节点 1 根本没被删到。4.2 用例二n1删除最后一个节点链表 1 → 2 → 3n 1。fast 从 dummy 走 2 步指向节点 2。循环开始第 1 轮fast 到 3slow 到 1第 2 轮fast 到 Noneslow 到 2。慢指针落在倒数第 2 个节点上也就是待删节点 3 的前驱。执行slow.next slow.next.next节点 2 直接指向 None链表变成 1 → 2最后一个节点被摘除。这个用例验证的是循环终止条件while fast is not None保证了 slow 不会自己走到链表末端而是精确地停在倒数第 2 个位置。4.3 用例三链表只有一个节点链表 1n 1。fast 从 dummy 走 2 步第 1 步到节点 1第 2 步到 None。循环不执行slow 停在 dummy。slow.next slow.next.next等价于dummy.next None返回dummy.next得到 None。也就是说删除唯一节点后链表变空。对这道题而言返回一个空链表是正确行为。这个用例同时也是最容易写崩的地方。如果你把 fast 初始化为 head 而不是 dummy或者 fast 先走的步数错误这里很容易在fast.next上抛空指针异常。用一个例子把这一步走通写的时候心里就有底了。4.4 非法输入的防御性写法题目通常保证 n 是一个合法的正整数且不大于链表长度。但到了真实工程里没人替你保证这件事。最稳妥的做法是在 fast 先走的循环里加一个越界检查for _ in range(n 1): if fast is None: return head # n 超过链表长度不做修改 fast fast.next这段防御代码不影响正确用例的性能但能避免在 n 大于链表长度时直接崩溃。做算法题时可以不加写工程代码时我建议保留。同理head 为 None 的链表走到fast.next之前先判空也能避免空指针。5. 面试追问与同类题的迁移5.1 面试官为什么死磕“遍历一次”很多人以为面试官只是在考一个优化技巧实际上他考察的是两个更底层的能力。第一你对单链表结构的理解是否到了“没有前驱指针就必须靠设计来弥补信息缺失”的程度。能用双指针说明你已经理解在单向结构里想知道相对位置可以用另一个指针保持间距。第二你的边界意识。这道题的代码核心只有几行但 head 被删、链长等于 n、链长等于 1 这些情况如果没有系统性地想清楚很容易在某一个用例上翻车。面试官通过追问“如果 n 等于链表长度呢”能快速判断你平时写代码到底有没有习惯性做边界检查。所以在面试中不要只背代码最好能主动把 4.1 到 4.3 的三个用例讲一遍。这比把代码写得一字不错更有加分效果。5.2 三句话讲清楚双指针解法如果你要在面试中表达这个解法我建议用下面这三句话既简练又完整第一句快指针先走 n1 步目的是让两个指针之间保持 n1 的间距。第二句之后两个指针同速移动快指针到达链表末端时慢指针与末端之间的距离正好是 n所以它停在倒数第 n1 个节点也就是待删节点的前驱。第三句此时执行slow.next slow.next.next不需要单独处理头节点因为 dummy 给了所有节点一个统一的前驱。这三句话是一个从“构造间距”到“利用间距”再到“统一删除”的完整逻辑链。面试官如果能听到这段推导而不是“我看到别人这么写的”印象会完全不同。5.3 从这一题延伸出的三个高频变体双指针在链表题里是一套通用思想这道题只是入门。掌握之后下面几个变体能顺带解决。变体一找倒数第 K 个节点但不删除。方法和本题几乎一样唯一区别是 fast 先走 k 步而不是 k1 步。这样 fast 到末尾时slow 正好指向倒数第 k 个节点本身定位完成。记住一个规律少走一步slow 指向目标本身多走一步slow 指向目标前驱。变体二找链表中间节点。快指针每次走两步慢指针每次走一步快指针到末尾时慢指针正好落在中点。判断回文链表时经常要先用到这一步。变体三判断链表是否有环。同样是一个走两步、一个走一步如果链表有环两个指针一定会在环内相遇。这个解法叫快慢指针逻辑和本题一脉相承。我自己写这题多年仍保留一个习惯任何双指针题写完先脑内跑三个极值用例——n1、n等于链表长度、链表只有一个节点。这三关能过基本不会再在提交时被边界打回。如果你也想把这道题真正转化成自己的东西建议把“找链表中间节点”和“判断环形链表”放在同一天刷它们用的是同一套间距逻辑放在一起理解比单独背这一题的效果好得多。