LeetCode 第 19 题“删除链表的倒数第 N 个结点”在刷题圈几乎是“必刷基础算法题”级别的存在。很多人会在各种刷题计划里看到它题号写着 19名字看着也通俗但真正上手写的时候很多人才发现这题并不像想象中那么轻松单链表只能从头往后走不能回头而你要删的偏偏是一个“倒数”位置的节点。如果你准备面试这题是双指针入门的绝佳素材如果你刚接触链表这题也能逼你把“遍历一次”这个说法想明白。这篇文章我会把双指针解法从原理到代码、从边界推演到实战坑点完整过一遍。适合刚开始刷链表题的初学者也适合那些“能 AC 但讲不清”的面试候选人。老实说这题能讲透你对单链表的理解基本就上一个台阶了。1. 先看这题到底在考什么1.1 “倒数第 N 个节点”为什么绕单链表的结构决定了它没有“从后往前”的能力。数组可以靠下标arr[len - n]瞬间定位到倒数第 N 个元素但链表里的每个节点只知道自己后面是谁不知道前面是谁更不知道总长度。所以你嘴上说“倒数第 N 个”实际上代码里根本没有“倒数”这个操作所有访问都得绕着弯来。打个比方一支队伍排成一列每个人只能拍一下前面人的肩膀问不出“你前面还有几个”只有走到队尾的人才知道自己是最后一个。现在要找出倒数第 5 个人你不能从队尾往前数因为往前走不通。唯一能做的就是让一个人先往前走出去一段距离再让另一个人和他保持固定差距一起走这样第一个人到终点时第二个人正好停在倒数第 5 个的位置。这就是双指针能一次遍历的核心原因。题目本身也不复杂给你一个单链表的头节点 head和一个整数 n要求删除链表的倒数第 n 个节点然后返回链表的头节点。1.2 两次遍历的常规解法和它的成本很多人第一反应是先遍历一遍链表数出链表长度 L然后从头再走 L - n 步找到目标节点的前一个位置做删除。这个思路非常直接也很好写第一次遍历统计节点数 L如果 L n说明要删的是头节点直接返回 head.next否则从头走 L - n - 1 步到达目标节点的前驱把前驱的 next 指向目标节点的 next。这个方案的时间复杂度是 O(2L)也就是 O(L)空间复杂度 O(1)。大部分情况下都能通过LeetCode 也接受。但面试官在讲完这个解法之后几乎一定会追问一句“能不能只遍历一次”你可能会觉得O(L) 和 O(2L) 不都是 O(L) 吗有什么差别从大 O 的角度确实一样但“遍历两次”和“遍历一次”在面试题里是两个境界。前者证明你懂链表后者证明你懂“怎么用指针关系省掉一次扫描”。在很多真实场景里数据源可能不是内存里的普通链表而是某种只能从头到尾访问一次的流式结构这时候“两次遍历”就不是常数优化问题而是能不能做的问题。2. 双指针解法为什么能一次遍历2.1 等距窗口双指针的原理拆解双指针的思路可以这样理解维护两个指针 first 和 second一开始都指向某个起点。先让 first 单独往前走 n 步这样 first 和 second 之间就拉开了一个长度为 n 的“窗口”。接下来两个指针同步往后移动每次各走一步。因为窗口距离始终固定所以当 first 走到链表末尾的 null 时second 和末尾的距离也正好是 n。但这里有一个非常关键的细节你真正想删的是倒数第 n 个节点而删除操作需要操作的是它的前驱节点。所以 second 最终停在哪里取决于你让 first 先走了多少步。如果 first 先走 n 步那么同步结束后 second 会停在“目标节点本身”如果 first 先走 n1 步那么同步结束后 second 会停在“目标节点的前驱”。两种都能写但后者更直接删起来更方便。很多新手写这题出错就是没想明白这层区别代码里 first 先走 n 步后面却直接写second.next second.next.next结果把一个好端端的节点漏删了或者删错了。2.2 先走 n 步还是先走 n1 步我用带哑节点 dummy 的写法来推演一遍。假设链表长度是 L在 head 前面加一个 dummy 节点那么整个链表的结构是dummy - node1 - node2 - ... - nodeL - null给每个位置编号dummy 是第 0 个节点node1 是第 1 个nodeL 是第 L 个null 是第 L1 个位置。如果 first 先走 n1 步它会走到第 n1 个节点这里假设 n L 时的情况。从第 n1 个节点走到 null还需要走 (L1) - (n1) L - n 步。同步期间 second 也从 dummy 出发走 L - n 步最终停在编号 L - n 的位置。编号 L - n 是什么概念倒数第 n 个节点也就是正数第 L-n1 个节点它的前驱编号正好是 L-n。所以 second 恰好停在目标节点的前驱之后一行second.next second.next.next就能完成删除。如果 first 先走 n 步那么 second 同步结束后会停在编号 L-n1也就是目标节点自己身上。这时候你还得额外记录一个 prev 指针或者在循环里判断什么时候停下逻辑就绕了一些。2.3 哑节点的价值让删除头结点不再特判用哑节点最重要的收益其实是处理“n L”这种极端情况。当链表长度正好等于 n 时要删除的是头节点。如果你用普通节点作为起点想找头节点的前驱会发现根本不存在。这时候要么写一个if判断要么用 dummy。而用了 dummy 之后dummy 就是头节点的前驱删除逻辑和删除其他节点完全一样不需要任何特判。dummy ListNode(0, head) second.next second.next.next # 就算删除的是 head也是合法操作 return dummy.next # 永远返回正确的头这个技巧不仅在这题有用。只要链表操作涉及“头节点可能被删掉”的场景比如按值删除所有节点、反转链表等先挂一个 dummy 哨兵节点永远是省心又稳的选择。它让“边界情况”变成了“正常情况”。3. 代码实现与逐步拆解3.1 Python 实现dummy 版本直接看代码。这里我用的是 first 先走 n1 步让 second 正好停在待删节点的前驱。class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]: dummy ListNode(0, head) first dummy second dummy # 先让 first 走 n1 步拉开距离 for _ in range(n 1): first first.next # 两个指针同步走直到 first 到 null while first: first first.next second second.next # 删除倒数第 n 个节点 second.next second.next.next return dummy.next每一步都很简单但每一步都有讲究。dummy ListNode(0, head)哑节点的值无所谓主要作用是让头节点也有一个“前驱”。first dummy、second dummy两个指针从同一起跑线出发。for _ in range(n 1)这里为什么是 n1 而不是 n因为我们要的是“前驱位置”。如果链表长度 L 5n 2first 先走 3 步会停在 node3。此时 first 离 null 还有 3 步second 同步走 3 步会停在 node3而 node3 正好是 node4 的前驱。while first:这个循环之所以能终止是因为链表最后一定是 null。只要 first 没到 null两个指针就一起动。second.next second.next.next直接把倒数第 n 个节点从链条中摘除。此时 second.next 就是要删的节点。return dummy.next无论删的是不是头节点dummy.next 都是新链表头。如果你写成return head当头节点被删时会返回一个已经被改过的节点结果就会错。3.2 C 实现与内存细节C 版本逻辑完全一样但多了一个内存管理的细节。链表节点的删除在 C 里意味着你要不要delete掉那个节点。class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0, head); ListNode* first dummy; ListNode* second dummy; for (int i 0; i n; i) { first first-next; } while (first ! nullptr) { first first-next; second second-next; } ListNode* toDelete second-next; second-next second-next-next; delete toDelete; ListNode* result dummy-next; delete dummy; return result; } };在 LeetCode 这种评测平台上节点内存由平台统一回收你不 delete 也能过。但在真实工程或本地联调时删除一个节点就应该把它的内存释放掉否则长时间跑会有内存泄漏。这里还有一个容易翻车的顺序问题先把要删除的节点指针保存下来再修改 next 指针最后 delete。如果你先改了second-next就再也拿不到被删节点的地址了那就没法安全释放。顺序反了会直接造成悬空指针或者内存泄漏。GitHub 上的许多题解为了简洁会省略 delete这没问题。但你心里得清楚刷题代码和工程代码是两码事。3.3 两种常见写法对比除了 dummy 方案还有一套常见的“不带头节点 特判”写法。我也列出来方便你对比面试时可以根据习惯选择写法first 起点first 先走步数循环条件second 最终位置头节点删除处理方式 Adummy 统一法dummyn1while first:待删节点前驱不需要特判dummy 就是前驱方式 B双指针特判法headnwhile first.next:待删节点前驱需要单独判断 first 是否已经为 null方式 C先走 n 步同删法headnwhile first:待删节点本身需要单独判断并记录前驱方式 B 的典型写法是class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]: first head for _ in range(n): first first.next if not first: return head.next second head while first.next: first first.next second second.next second.next second.next.next return head这里 first 先走 n 步然后while first.next让 second 停在目标前驱逻辑也成立。但注意它需要单独处理“删除头节点”的场景——如果 first 走完 n 步已经是 null说明 n L要删的就是 head返回 head.next。方式 B 在面试里也很常被写出来不算错只是分支比方式 A 多了一点。我个人更推荐方式 A因为它把特判消灭在了数据结构层面代码更短思路也更统一。你不需要在脑子里记住“什么时候 first 是 null”、“什么时候 second 会越界”只要坚信“有 dummy 就有前驱”就够了。3.4 复杂度分析时间是 O(L)空间是 O(1)双指针方法的时间复杂度是 O(L)空间复杂度是 O(1)。这里的 L 是链表长度。时间first 总共走了(n1) (L-n) L1步second 走了L-n步整体就是 O(L)。空间只额外创建了一个 dummy 节点和两个指针变量不随链表长度增长而增长是 O(1)。对比一下用哈希表记录每个节点位置的做法——虽然也能一次遍历但你需要一个长度为 L 的 map 来存节点空间变成 O(L)。双指针最大的优势正是“不记录中间状态”只凭两个指针的相对位置关系就完成了任务。4. 常见错误、边界与调试实录4.1 最容易踩的 5 个坑这题虽然代码短但我见过太多种错误写法在这里集中列一下。错误类型可能原因修正方案头节点被误删后返回旧 head没意识到head本身可能被删使用dummy.next作为返回值删除节点时 second 停在目标节点上first 先走 n 步却直接用second.next.next改为 first 先走 n1 步或用while first.next循环条件写错导致指针多走一步while first.next和while first混淆在纸上推演一遍再编码链表为空或 n 超过链表长度时崩溃缺少防御性检查先判断 head 是否为 null题目一般默认输入合法但工程中要加C 删除节点顺序不对先改 next 再取删除节点先保存toDelete second-next改链再 delete第一个坑非常典型。很多人写完后拿普通用例测一看结果全都对但是一旦 n 等于链表长度删除的是头节点return head返回的还是那个头节点但它已经被摘出去了打印出来会是错误结果。这种问题跑几个单节点用例就能暴露。第二个坑则是“步数错觉”。很多人心里想的是 second 要停在目标节点的前驱结果代码里让 first 先走 n 步又用while first循环最终 second 停在目标节点自己身上删错了。我的建议是动手写之前先在代码注释里明确写出 second 最后必须停在哪再决定 first 走几步。4.2 用具体例子把指针走一遍光看理论容易晕我以下面这个例子实际走一遍链表1 - 2 - 3 - 4 - 5n 2。预期结果删除倒数第 2 个节点也就是节点 4最终链表为1 - 2 - 3 - 5。用方式 Adummy first 先走 n1 步推演步骤first 位置second 位置初始化dummydummyfirst 走第 1 步node1dummyfirst 走第 2 步node2dummyfirst 走第 3 步node3dummy同步走第 1 步node4node1同步走第 2 步node5node2同步走第 3 步nullnode3结束时 second 停在 node3是 node4 的前驱。执行second.next second.next.nextnode3 的 next 从 node4 指向 node5链表变成1 - 2 - 3 - 5。完美。如果换成极端情况链表1n 1。预期结果空链表返回 null。步骤first 位置second 位置初始化dummydummyfirst 走第 1 步node1dummyfirst 走第 2 步nulldummy同步循环完全不会进入second 停在 dummy执行删除后 dummy.next 指向 null返回 null。你看头节点被删的情况在 dummy 方案里不需要任何 if 分支非常干净。4.3 面试现场怎么表达思路如果面试遇到这题口头表达的顺序比写代码更重要。我建议按下面这个节奏说先说核心结论“我需要找到待删节点的前驱。单链表没法回溯所以我用两个指针拉开固定距离first 先走second 再跟当 first 到终点时 second 正好在前驱位置。”再说边界“头节点可能被删所以我会加一个 dummy 哨兵节点让头节点也能像普通节点一样被统一处理。”后说做法“first 从 dummy 出发先走 n1 步然后和 second 一起走直到 first 为空此时删除 second.next。”最后补复杂度“时间 O(L)空间 O(1)。”这个顺序会告诉面试官你不只是背过题解而是真的理解为什么要这么做。尤其是“为什么是前驱”和“为什么需要 dummy”这两点几乎一定会被追问提前想清楚会从容很多。5. 从这题延伸出去双指针在链表题里的应用5.1 一类题快慢指针的三种用法这道题用的双指针本质上是一个“固定步差”的技巧。双指针在链表题里其实有三种常见形态理解了这题之后其他题目就能串起来了。固定距离型本题就是典型。两个指针速度相同但出发位置不同先走一步的指针和另一个指针之间始终保持固定距离。类似的还有“链表中倒数第 k 个节点”把本题中的删除去掉就是找倒数第 k 个节点。速度差型快指针每次走两步慢指针每次走一步。经典应用是求链表的中间节点876 题以及判断链表是否有环141 题。快指针走完时慢指针正好在中点快指针如果追上了慢指针说明存在环。交换汇合型两个指针从不同链表出发走到头后互相切换起点最终在交点汇合。比如 160 题相交链表本质上是把两个链表的路径差抹平。你只要把这三种形态都想明白再做其他链表题会轻松很多因为很多题就是在这三种模式下换了个外壳。5.2 如果题目换成一维数组思路还成立吗双指针不只在链表上生效。数组里的双指针同样到处可见只是数组不需要 next 指针而是通过下标移动。比如 27 题“移除元素”用快慢指针快指针遍历数组慢指针负责记录“被保留下来的位置”和链表里双指针找位置的思想非常像。再比如滑动窗口类的题本质也是左右两个指针构成一个窗口右边扩展左边收缩这也是双指针。所以这题学到的东西并不仅限于链表而是一种更通用的思维能不能用两个元素之间的关系替代掉“先整体扫描一遍拿到信息”的做法。这也是为什么面试官总爱问双指针。5.3 为什么“一次遍历”在工程里也有意义有人会觉得刷题里说“一次遍历”现实中链表都在内存里多遍历一次无非是慢了一点有那么夸张吗在一些场景里确实有实打实的收益。假如链表很长很长长到节点数据不是全部常驻内存而是通过流式接口从磁盘或网络里一条一条读出来的那么“遍历两次”可能意味着你要么把数据缓存下来要么重新拉取一遍数据成本就不再是常数倍了。双指针方案只需要你记住两个指针位置就能在数据流过一遍的情况下完成操作这在单次数据访问受限的系统中很有价值。我再举个例子你拿到一个只能访问 next、不能跳跃的输入源类似于一个不可随机访问的流这时候如果想知道某个元素离末尾有多远你只有两个选择——要么把整个流存下来回放要么用固定间距的“先遣指针”提前探测。双指针正是先遣指针的思想。说到这里我个人后来再刷这道题会刻意要求自己不看题解写出三种版本两次遍历版、dummy 双指针版、不带 dummy 的特判版。不是为了炫技而是每次写完用[1]、[1,2]、[1,2,3,4,5]这三个输入各跑一遍再手动推一次指针位置差不多 10 分钟就能把边界条件练成肌肉记忆。面试时最怕的不是不会而是会了但不知道什么时候翻车——提前把这些小样例跑熟是躲开这类低级错误最笨也最有效的方法。