刷 LeetCode 的朋友对第 19 题不会陌生删除链表的倒数第 N 个结点。这个题被划在“链表中级”一档但真动手写的时候很多人第一反应是先遍历一遍拿到链表长度再走一遍去删目标节点。这种做法当然没问题但如果面试官追问一句“能不能只遍历一次”思路就得换成双指针。这篇文章就从这道题出发把双指针一次遍历的来龙去脉、手写细节、边界条件和容易踩的坑一次说清楚。题目不长但背后藏着的思考方式能帮你打通不少链表题目。1. 题目到底在考什么先看懂暴力解法和双指针的意图1.1 题目描述和最容易想到的两遍扫描题目说的是给一个单链表给定整数 n删除从链表尾部数的第 n 个节点然后返回头节点。比如链表1 - 2 - 3 - 4 - 5n 2删除的是 4最后返回1 - 2 - 3 - 5。最直观的思路是先扫一遍链表数出长度 L然后知道倒数第 n 个节点就是正数第 L - n 1 个节点要删它就要找到它的前驱也就是第 L - n 个节点。走到那里把prev-next prev-next-next一改完事。这个思路没有任何问题复杂度是 O(L) 时间O(1) 空间。但问题在于它遍历了两遍一遍数长度一遍走删除。面试如果只是让你做出来这可能够了但如果面试官强调“你能否只扫描一趟完成删除”你就需要把思路切换到双指针上。1.2 为什么“倒数第 N 个”天然适合双指针链表这个东西和数组不一样它没有随机访问你不知道当前节点是第几个更不知道距离尾部还有多远。想一次遍历就定位倒数第 n 个节点最自然的办法就是制造一个长度差。你可以想象两个人赛跑一个跑得快一个跑得慢。先让快的人提前跑 n 步然后两个人保持同样的速度一起前进。等快的人跑到终点链表末尾的 null时慢的人和快的人之间的距离始终是 n 步所以慢的人刚好站在倒数第 n 个节点的位置上。这就是双指针法最核心的思想。不过这里有一个关键的细节删除节点需要知道它的前驱节点。如果慢指针正好停在倒数第 n 个节点上你是没法直接删掉它的——你只能拿到这个节点本身无法访问它前面的节点。所以在实现的时候我会让慢指针停在倒数第 n 1 个节点也就是待删节点的前驱上这就需要一个虚拟头节点的帮忙。提示链表的删除操作本质上是在改某个节点的 next 指针。如果待删节点是头节点你没有前驱可用所以统一用虚拟头节点dummy处理能省去一堆 if 判断。2. 双指针核心原理快指针先走 N 步慢指针负责停在目标前驱2.1 一次遍历的精髓制造长度差我直接讲最常用的实现方式也是官方题解里的版本创建一个虚拟头节点dummy让dummy.next head。定义快指针fast和慢指针slow。我习惯让fast从真正的头节点出发让slow从dummy出发。让fast先走 n 步。然后让fast和slow一起走每次各走一步直到fast走到 null。此时slow.next就是倒数第 n 个节点执行slow.next slow.next.next完成删除。返回dummy.next。为什么slow初始指向dummy而不是head因为我们要让最终停顿点落在待删节点的前驱上。我画一个演示过程链表是dummy - 1 - 2 - 3 - 4 - 5假设 n 2初始fast 1slow dummy 第一步fast 先走 2 步到 3 然后同时走 fast 到 4slow 到 1 fast 到 5slow 到 2 fast 到 nullslow 到 3此时 slow 指向 33 是倒数第 2 个节点 4 的前驱所以执行slow.next slow.next.next就把 4 删掉了。整个过程中快指针扫了一遍链表慢指针跟着扫了一遍两者一共走了大约 L 步而不是 L 遍因此是真正的一次遍历。2.2 快指针走 N 步还是 N1 步这里最容易混我看过不少人的笔记发现大家卡得最多的点是为什么有的写法里fast先走 n 步有的写法里先走 n 1 步这和slow的初始位置是配套的。我说一个通用的判断方法关键看你想让最终slow停在哪。如果fast初始在headslow初始在dummy那么fast先走 n 步之后两者之间已经隔着 n 个“距离”。一起走时fast到 null 时slow距离 null 还有 n 步所以它指向倒数第 n 1 个节点即待删节点前驱。如果fast和slow都初始在dummy那你必须让fast先走 n 1 步也就是比待删节点多走一步这样slow才能刚好落在前驱上。如果fast和slow都初始在headfast先走 n 步那么fast到 null 时slow停在倒数第 n 个节点上这是目标节点本身不是前驱删除时会很尴尬。所以你可以发现不同的初始位置对应不同的步数没有唯一的“标准答案”。但面试时最好固定一种写法我自己的习惯就是第 2.1 节那套思路最不容易乱。注意无论怎么写快指针先走的那几步不计入“共同遍历”的过程。整段操作里链表最多被从头到尾访问一次空间上只有两个指针O(1)。3. 代码实现Python 和 C 双版本逐行拆解3.1 Python 实现简洁直接如果你用 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 head slow dummy # fast 先走 n 步 for _ in range(n): if fast is None: return head # 链表长度不够 n题目通常保证 n 有效防御用 fast fast.next # 两个指针一起走到 fast 为 None while fast: fast fast.next slow slow.next # slow.next 就是要删的节点 slow.next slow.next.next return dummy.next这段代码的核心就三步走 n 步、同步走、改 next。需要注意Python 里ListNode(0, head)这种写法依赖构造函数的第二个参数如果你用的是 LeetCode 默认的ListNode类它的构造函数本身支持ListNode(val0, nextNone)所以没问题。我在代码里加了一个防御判断如果fast还没走满 n 步就变成None说明链表长度不足 n题目输入不会出现这种情况但你写给自己项目里的通用工具函数时这种保护能让函数更健壮。如果不加fast为None后还要执行fast.next会直接抛空指针异常。3.2 C 实现注意内存释放C 版本和 Python 逻辑完全一样但多了手动管理内存这一步struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0, head); ListNode* fast head; ListNode* slow dummy; // fast 先走 n 步 for (int i 0; i n; i) { if (fast nullptr) { // 题目保证 n 合法这里只是为了防御 return head; } fast fast-next; } // 同步移动 while (fast ! nullptr) { fast fast-next; slow slow-next; } // 删除节点 ListNode* target slow-next; slow-next slow-next-next; delete target; // 返回新头并释放虚拟头节点 ListNode* newHead dummy-next; delete dummy; return newHead; }为什么 C 里slow-next slow-next-next之前要单独保存target因为一旦修改了slow-next原来那个节点的指针就不容易拿到了不保存直接改后面就没法delete会造成内存泄漏。刷题时 LeetCode 不会盯着你内存泄漏但面试里如果要求写完整 C这属于基本功。3.3 边界条件与防御性写法边界条件永远是链表题的命门。我总结一下这段代码处理三种情况的机制第一删除的是头节点。比如链表1 - 2n 2要删 1。按代码流程fast走 2 步后正好变成nullslow还在dummywhile循环一次都不会进slow-next就是原来的头节点 1执行删除后返回dummy-next也就是新的头节点 2。这一步如果没有dummy要单独处理“删除头节点”的情况很容易漏。第二n 等于链表长度。这种情况等价于删除头节点上面已经覆盖了。第三链表长度为 1n 1。fast走 1 步后为nullslow在dummy删除dummy-next返回null。逻辑依然成立。所以虚拟头节点最大的意义就是让“头节点”和“普通节点”的删除逻辑完全统一不用在代码里写一个if (head null || n 1)的旁路分支。4. 实操中的坑从“报错”到“一次过”4.1 很容易翻车的三个边界细节第一指针初始位置搞错。我见过很多人把slow也初始化为head结果删不掉目标节点或者删了错误的节点。你要记住slow必须落后fast足够的距离并且要落在前驱上。最简单的方法就是照着第 2.1 节的初始化来不要随意改。第二循环结束条件的判断。有些版本会写while (fast-next ! nullptr)这时快指针走到最后一个节点就停了slow的位置会差一个节点。和前面的步数选择是对应的但没有统一的推导就很容易出错。我的建议是直接以fast null作为结束条件和“快指针到达终点”的概念一一对应。第三没有处理空链表或 n 非法。普通项目里如果输入 n 大于链表长度你没保护就会直接段错误。我建议在“快指针先走 n 步”的循环里加一个空指针判断这样对异常输入也能安全退出。4.2 常见问题排查速查表我在实战中把容易踩的坑整理成了一张表写代码之前可以对照看一眼症状可能原因解决办法删除之后头节点没了删了 head 但返回了原 head返回dummy-next别返回原head删除的是倒数第 n-1 个节点快指针先走步数不对按初始位置推导确认是先走 n 步还是 n1 步出现空指针异常链表长度小于 n没加防御在走 n 步的过程中检查fast null内存泄漏C没有 delete 被删节点先保存target slow-next再断开循环结束后 slow 位置不对同步走时条件写成了fast-next ! null统一为while (fast ! null)题目要求的“只遍历一次”没满足先求长度再删直接用双指针不要额外扫描这张表不是背的是写错之后对着调试用的。我当时第一次提交就挂在“删了头节点返回了原 head”上因为没建 dummy后来换成虚拟头节点一次过。5. 举一反三双指针在链表题里的其他战场5.1 寻找链表中点一快一慢速度不同链表中点也是一道高频面试题。思路是slow每次走一步fast每次走两步当fast到达末尾时slow正好在中点。代码非常简单def middleNode(head: ListNode) - ListNode: slow fast head while fast and fast.next: slow slow.next fast fast.next.next return slow这和删除倒数第 N 个节点的思路同源都是快慢指针制造“路程差”。你做熟了这道题再看中点问题会感觉非常亲切。5.2 判断链表是否有环快慢指针相遇判断链表有没有环另一个经典应用。如果有环fast进入环之后迟早会追上slow两人相遇就是有环如果fast走到 null就是无环。def hasCycle(head: ListNode) - bool: slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False我之前刷题的时候第 19 题、876 题、141 题连着做发现它们全是同一套双指针思想只是速度差和起点不同而已。5.3 从这道题延伸出的思维模型如果你把“删除倒数第 N 个结点”想通了你应该有能力自己推导很多变体删除链表的中间节点先找中点再删两个指针就能搞定。求倒数第 N 个节点不删除只返回节点那就让slow直接停在目标节点上快指针先走 n 步后同步走fast到 null 时slow就是答案。旋转链表右移 k 位本质也是快指针先走 k 步然后快慢一起走找到新头的前驱。这些都是同一种“先制造长度差再同步推进”的模型。所以我特别建议你把第 19 题当作双指针入门的第一课思路通了后面会轻松很多。5.4 为什么不用栈或递归也许有人会问一次遍历也能用栈先全部压栈再弹出 n 个弹到第 n 个时删除。或者用递归回溯时计数。这两种方式当然也能实现但需要 O(n) 的额外空间。双指针只需要两个指针节点空间 O(1)。在链表题里空间复杂度往往和面试官出题意图直接挂钩遇到“能否只扫描一次”这种限制时双指针才是符合题意的答案。我刚才重新写了一遍完整的 C 版本在本地加了几个测试用例跑了一遍包括链表长度为 1、n 1删头节点以及正常删除中间节点。kena感觉最稳的还是哑节点那套写法逻辑统一不容易改错。这道题代码不到二十行但你要真的吃透它的指针位置推导而不是死记“fast 先走 n 步”否则面试官换个初始条件把你一问你很容易露馅。下次再看到链表题可以先想想能不能用快慢双指针制造距离差很多看起来绕的问题其实就是多走几步的距离差问题。