企业官网建设流程全解析

每日一题：删除链表倒数第N个节点

这道题我至少见过它在三十多场模拟面试和算法讨论里出现，说它是链表题里的“基本功试金石”一点都不夸张。题目描述很简单：给一个单链表，删除倒数第N个节点，返回头节点。但就是这么一道“简单题”，能把指针操作、边界处理、空间复杂度优化一次全考到位。无论是刚开始刷链表题的新手，还是准备技术面试的开发者，这道题都值得认认真真拆一遍。

我最早做这题的时候也栽过跟头——快指针先走N步还是N+1步？要不要用哨兵节点？N刚好等于链表长度时怎么办？这些细节单独看都不难，但凑到一起就特别容易翻车。这篇文章我想把这道题的完整思考链路、三种实现版本、边界条件、以及我在实际调试中踩过的坑一次讲清楚，帮你把这题吃透。

1. 题目拆解与思路定位

1.1 题面解读：这道题到底在考什么

先看最关键的约束条件。链表是单向的，这意味着你没法从尾部往回走。要删倒数第N个节点，最原始的想法是先数出链表长度L，然后从头走到第L-N个节点，把它后面的节点删掉。这个思路没错，也是很多人的第一反应。

但注意题目不限制N的范围吗？经典版本通常会保证N是有效的，不过尽管理论上可以不处理非法N，写代码时还是要有基本的防御意识。你后面就会发现，很多边界case恰恰来自对N和链表长度的关系没想清楚。

这道题真正想考的东西有三层：

• 第一层：能不能想到双指针（快慢指针）这种一次遍历的方案
• 第二层：能不能正确处理头节点被删除的特殊情况
• 第三层：能不能把循环条件和指针移动的细节说清楚，而不是“背模板”

我把第三层单独拿出来说，是因为太多人写完双指针代码能跑通，但被问到“为什么快指针要先走N步而不是N+1步”时就卡住了。面试官其实不在乎你背没背过模板，他在乎的是你懂不懂指针之间距离变化的原理。

1.2 双指针解法的直觉来源：为什么快慢指针能一步到位

双指针解法的直觉，用一句话说就是：让快指针比慢指针先走N步，然后两个指针以相同速度前进，当快指针走到链表末尾的null时，慢指针正好停在倒数第N个节点的前一个位置。

这个直觉来自一个很朴素的距离关系。假设链表长度为L，头节点位置记为1。那么倒数第N个节点在正数方向的位置是 L-N+1。它的前驱节点位置是 L-N。快指针先走N步，到达位置N+1；接着两指针同步走，当快指针走到位置L+1（也就是null）时，它一共走了 L-N 步。慢指针从位置1出发，同样走 L-N 步，恰好到达位置 L-N+1？等等，这里需要仔细算一下。

慢指针初始在位置1，走 L-N 步，到达的节点位置是 1 + (L-N) = L-N+1。这正好是倒数第N个节点本身啊？不对，我上面说的是“前一个位置”。这里其实涉及一个常见的混淆点：

• 如果快指针先走N步，那么快指针初始位置是 N+1。两指针同步走，快指针到达null（位置L+1）需要走 (L+1) - (N+1) = L-N 步。慢指针走 L-N 步后停在位置 L-N+1，也就是倒数第N个节点本身，不是它的前驱。
• 如果要停在前驱位置 L-N，那快指针应该先走 N+1 步。

两种都能做，区别在于删除操作的写法。停在目标节点本身时，你需要额外记录一个 prev 变量跟踪前驱；停在目标前驱时，直接改 next 指针就行。

大多数实现选的是“先走N步”，配合哨兵节点后，慢指针最终停在目标节点的前驱，因为哨兵节点让所有位置计数都偏移了1。这个细节放到第3部分代码里会看得更清楚。你现在只需要记住核心思想：两个指针之间保持固定距离，用快指针的“到头”来锚定慢指针的位置，这就是一次遍历删倒数第N个节点的全部秘密。

1.3 哨兵节点（Dummy Node）的价值：头节点被删时的“保护伞”

很多人写链表题不喜欢加哨兵节点，觉得“多此一举”。但删除倒数第N个节点这题，哨兵节点几乎是必须的，原因很简单：当N等于链表长度时，要删的是头节点本身。

没有哨兵时，删除头节点必须单独写一段逻辑：

if N == length: head = head.next return head

这倒也不是不能写，但容易漏。而且如果你用的是双指针方案，删除头节点时快指针先走N步，直接走到了null，此时如果把慢指针的 next 指向 next.next，就报空指针异常了。有了哨兵节点 dummy，这个问题直接消失：

• dummy.next 指向 head
• 快指针从 dummy 出发先走N步
• 快慢同步走，直到快指针到null
• 慢指针停在目标节点的前驱，执行删除
• 返回 dummy.next 作为新头节点

哨兵节点的本质是把“头节点的删除”和“中间节点的删除”统一成同一种操作。它不改变算法复杂度，只是让边界条件不再需要特判。我自己写链表题的经验是：凡是涉及“删除头节点可能被删”的题目，无脑加哨兵，能把注意力集中在核心逻辑上。

2. 核心细节与边界条件剖析

2.1 快指针到底先走N步还是N+1步：一字之差，天壤之别

我见过大量讨论区代码在这个细节上翻车。先明确两种模式的差别：

• 先走N步：快指针从哨兵出发，先走N步。之后快慢同步。快指针到达null时，慢指针指向倒数第N+1个节点（即目标节点的前驱）。此时删除操作为slow.next = slow.next.next。
• 先走N+1步：快指针从哨兵出发，先走N+1步。之后快慢同步。快指针到达null时，慢指针恰好指向倒数第N个节点（目标节点本身）。此时你得再维护一个 prev 指针，删除操作为prev.next = slow.next。

看出差别了吗？先走N步更简洁，因为它配合哨兵天然把慢指针停在了前驱位置。先走N+1步也能做，但代码会多一个变量，循环条件也更容易写错。

为什么很多人写错？因为他们背结论时没理解“从哨兵出发”和“从head出发”的区别。如果从head出发，快指针先走N步，那么当快指针到null时，慢指针指向的是目标节点本身而不是前驱——注意，这与从哨兵出发的结论不同。所以网上的代码五花八门，其实都没错，只是起点不同导致结论不同。你写代码前先想清楚自己的起点是dummy还是head，然后严格推演一遍指针的距离，就不会乱。

我在面试时如果看到候选人写“先走N步”的版本，会追问一句：如果快指针先走N步，慢指针停在哪？能答出“倒数第N+1个，或者说目标节点的前驱”，我就知道他是真的理解了。

2.2 边界条件逐一攻破：N等于链表长度、单节点链表、N的合法性

边界条件是这题最容易扣分的地方。我列一张表，你对照着检查自己的实现：

最典型的坑是“N等于链表长度”和“单节点链表”这两个case，本质上是一回事：要删的是头节点。如果没加哨兵，你得特判；加了哨兵，逻辑完全不用变。我见过很多候选人自信满满地说“我的代码没问题”，结果一跑[1], 1这个case就挂了。

至于N的合法性，经典题目版本里N被保证是有效的，但你自己实现时建议加一层判断：如果N小于等于0，或者N大于链表长度，直接返回原链表。这个防御逻辑不复杂，却能让你在面试中多一个“考虑健壮性”的加分点。

2.3 复杂度分析：为什么双指针是最优解

双指针解法的时间复杂度是O(L)，其中L是链表长度，因为快慢指针合计遍历了一遍链表。空间复杂度是O(1)，只用了两个指针变量，没有额外的存储结构。

这已经是最优解了。有些语言（比如Python/Lisp风格的递归）可以用递归倒序遍历来模拟“从后往前数”，但递归的调用栈深度等于链表长度，空间复杂度是O(L)，在链表很长时有栈溢出风险，实际工程里几乎不会这么写。

还有个常见思路是：先遍历一次拿到链表长度L，再遍历第二次到达 L-N 位置执行删除。这个方案时间复杂度也是O(L)，代码更直观，适合作为切入解法，但它多了一次遍历。面试官通常会追问“能不能只遍历一次”，这时候再引出双指针，节奏刚刚好。

3. 手把手实现：版本演进与完整代码

3.1 第一版：两次遍历的直观方案

先从最直观的版本开始写。这个版本思路简单：第一遍数长度，第二遍找位置。适合作为你理解题意的起点，也是我在白板上最先画的草图。

def remove_nth_from_end_two_pass(head, n): # 空链表直接返回 if head is None: return None # 第一遍：计算链表长度 length = 0 cur = head while cur: length += 1 cur = cur.next # 防御：N不合法则原样返回 if n <= 0 or n > length: return head # 要删除的是头节点 if n == length: return head.next # 第二遍：找到目标节点的前驱 steps = length - n - 1 # 从head走 steps 步，到达倒数第N+1个节点 cur = head for _ in range(steps): cur = cur.next cur.next = cur.next.next return head

这个版本最容易理解，但有个细微点要注意：steps = length - n - 1。为什么是减1？因为倒数第N个节点的前驱，在正数方向是第 length-n 个节点。从第1个节点（head）走到第 length-n 个节点，中间要移动 length-n-1 次。这块很容易算错，建议你手动拿一个5节点链表演示一遍。

这段代码的时间是O(L)，空间O(1)，功能完全正确。但它确实跑了两次循环。面试时你可以先给出这个版本，然后说“能优化到一次遍历”，这就是自然的引导。

3.2 第二版：双指针一次遍历

这是面试的标准答案。我用的是“哨兵节点 + 快指针先走N步”的组合。

def remove_nth_from_end_one_pass(head, n): dummy = ListNode(0) dummy.next = head fast = dummy slow = dummy # 快指针先走n步 for _ in range(n): fast = fast.next # 快慢指针同步走，直到快指针到达链表末尾 while fast and fast.next: fast = fast.next slow = slow.next # 此时slow指向倒数第N+1个节点，即目标节点的前驱 slow.next = slow.next.next return dummy.next

核心逻辑就这几行。我拆开讲一下为什么它是正确的：

1. fast = dummy后先走n步，此时 fast 指向正数第n个节点（从1开始计数），slow 仍在dummy。
2. while fast and fast.next:这个循环条件有两个作用：一是保证 fast 不会变成None后才访问属性；二是在 fast 到达最后一个节点时停下来。此时 slow 跟着走了 L - n 步，从dummy出发，到达的位置恰好是倒数第N+1个节点。
3. 执行slow.next = slow.next.next完成删除。

这里有个容易纠结的点：为什么循环条件不写成while fast:？如果写成while fast:，fast 会一直走到 null，slow 也会多走一步，最终出现在倒数第N个节点上，删除操作就变成slow.next = slow.next.next直接空指针。这是一个非常经典的错误，我第4部分单独讲。

dummy.next作为返回值也处理了“删除头节点”的情况：如果N等于链表长度，fast 先走N步后指向null（假设链表长度刚好N），循环不执行，slow还在dummy，执行slow.next = slow.next.next，把 head 摘掉，返回 dummy.next 就是原来的第二个节点。分毫不差。

3.3 第三版：递归解法与它的代价

递归解法可以“假装”从链表尾部往回数，代码非常优雅，但不是这题的推荐答案，只做了解。

def remove_nth_from_end_recursive(head, n): # 用一个包装类避免global/nonlocal的麻烦 class Wrapper: def __init__(self): self.count = 0 def helper(node, w): if node is None: return None node.next = helper(node.next, w) w.count += 1 if w.count == n: return node.next return node dummy = ListNode(0) dummy.next = head w = Wrapper() dummy.next = helper(dummy, w) return dummy.next

这个解法利用递归回溯时的计数器来定位。每层递归返回时计数器加1，当计数器等于n时，说明当前节点是倒数第N个，于是跳过它。实际测试这个版本能跑通，但有两个明显问题：

第一，递归深度等于链表长度，链表一长就栈溢出。第二，理解和调试成本远高于双指针。所以我在面试中不会主动提这个解法，除非面试官明确要求。它存在的意义是帮你理解“递归天然具备回溯特性”，仅此而已。

3.4 测试用例设计：实战该怎么验

写完代码不是结束，你得有一套快速验证的手段。我通常会用一段测试代码把边界case全覆盖：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def build_list(arr): dummy = ListNode(0) cur = dummy for x in arr: cur.next = ListNode(x) cur = cur.next return dummy.next def list_to_array(head): arr = [] while head: arr.append(head.val) head = head.next return arr def test_remove_nth(): # case 1: 正常中间节点 head = build_list([1, 2, 3, 4, 5]) assert list_to_array(remove_nth_from_end_one_pass(head, 2)) == [1, 2, 3, 5] # case 2: 删除尾节点 head = build_list([1, 2, 3, 4, 5]) assert list_to_array(remove_nth_from_end_one_pass(head, 1)) == [1, 2, 3, 4] # case 3: 删除头节点 head = build_list([1, 2, 3, 4, 5]) assert list_to_array(remove_nth_from_end_one_pass(head, 5)) == [2, 3, 4, 5] # case 4: 单节点 head = build_list([1]) assert list_to_array(remove_nth_from_end_one_pass(head, 1)) == [] # case 5: 两个节点删头 head = build_list([1, 2]) assert list_to_array(remove_nth_from_end_one_pass(head, 2)) == [2] print("全部测试通过") test_remove_nth()

这五个case覆盖了：中间节点、尾节点、头节点、单节点、双节点删头。我建议你把这组测试沉淀成自己的一个小工具函数，后面刷链表题都能复用。实测下来，凡是能通过这五个case的双指针实现，基本不会再有别的问题。

4. 常见问题与排查技巧实录

4.1 指针丢失：为什么删完链就断了

这是链表题新手最经典的错误。下面这段代码就是典型的“链断了但你没发现”：

slow = slow.next # 只是移动了指针，没有修改任何节点的next slow = None # 直接把自己指向了None，链表结构没变

正确的删除必须修改前驱节点的 next 指向，而不是把目标节点变量置空。slow.next = slow.next.next这句的意思是：让前驱节点跳过目标节点，直接指向目标节点的后继。你要把它和“移动一个指针变量”区分开。一个形象的类比：删除链表节点不是把这个节点“烧掉”，而是把铁链上的这个环从两端解开，然后把前后两个环直接扣上。

所以写完删除逻辑后，检查三件事：前驱的next指向是否跳过了一个节点？返回的头节点是否还是有效节点？被删除节点的 next 是否已经被断开（如果没有，在某些语言里会保持引用，但不影响链表访问路径）？

4.2 空指针越界：快指针走过头了怎么办

把循环条件写成while fast:是最常见的空指针来源。我模拟一下过程：假设链表5个节点，N=5，fast从dummy先走5步后已经指向null。此时如果循环条件写while fast:，循环体里的fast = fast.next直接对None操作，立刻抛 AttributeError。

即使你侥幸让fast进入循环前不是None，while fast.next:这种条件也要求 fast 本身非空，否则一样炸。正确的防御方式有两种：

• 循环条件写while fast and fast.next:，先确认 fast 不为空再访问 fast.next。
• 在快指针走完之后加一个判断：if fast is None: return dummy.next，提前处理N等于链表长度的情况。

我推荐前者，因为它让循环自己和“走到最后节点停下”的语义对齐。这个错误的排查方法也很简单：给出一张5节点的链表，手动模拟N=5时的指针轨迹，你会立刻发现 fast 在步数走到 null 时，循环体根本不应该再执行第二次。

4.3 头节点特殊处理：dummy节点的真正威力

第2部分已经提过，这里再展开一下没有dummy会怎样。不用dummy写双指针，代码会长这样：

def remove_nth_from_end_no_dummy(head, n): fast = head slow = head # 快指针先走n步 for _ in range(n): fast = fast.next # 如果fast已经为空，说明要删的是头节点 if fast is None: return head.next # 快慢同步走，快指针指向最后一个节点时停下 while fast.next: fast = fast.next slow = slow.next slow.next = slow.next.next return head

这段代码也能跑对，但多了一个if fast is None: return head.next分支。问题不在于多这一行，而在于你每次写都要记得这个分支。一旦忘了，N等于链表长度时就会空指针崩溃。

dummy的精髓就在于：它把你从“特判头节点”这件事里解放出来。让我用一个比喻解释：dummy就像给单链表加了一个虚拟的“哨兵入口”，无论你要删的是原头节点还是中间节点，对代码来说都只是一次普通的“跳过下一个节点”操作。返回值统一是 dummy.next，不会出现“头节点被删但返回了旧head”这种逻辑错乱。

4.4 面试追问：从“能写出来”到“讲明白”

我模拟面试时经常把这题作为“热场题”，因为它能从浅到深问出好几个层次。常见的追问有：

追问1：为什么要用快慢指针？答：为了O(1)空间下一次遍历。注意这里不能只答“快慢指针”，要补充说明两指针保持N步距离的推理过程。

追问2：如果N非常大会怎样？答：题目保证N有效，但如果考虑健壮性，应该在移动快指针时判断是否越界。一旦 fast 在走N步过程中变成 None，说明N超过链表长度，直接返回原链表。

追问3：能不能用栈？答：可以，先遍历压栈，然后弹出N个节点，栈顶就是要删节点的前驱。时空复杂度都是O(L)，空间不如双指针，但思路也是一种选择。

追问4：如果要删除倒数第N个节点并返回被删节点的值，怎么做？答：在删除前先保存slow.next.val，删除后返回即可，其他逻辑不变。

我建议你把这些追问当成一个小型题库去准备。因为这题太常考了，你多准备一层，面试时就能多一层自信。实际上面试官要的不是候选人多快把代码写出来，而是看他能不能在写完后清晰地讲出“为什么这样写不会出边界问题”。能讲明白，比代码本身更值钱。

最后分享一个小体会。删除链表倒数第N个节点这题，做完之后最有价值的收获不是记住了一个模板，而是理解了“两个指针之间的固定距离”这个思想。同样的距离差技巧，可以用在找链表中间节点、判断链表是否有环、寻找环的入口这些题目上。你把这题吃透了，后面遇到一类链表问题都会轻松很多。我当时就是把这题反复推演了三五遍，把每一步指针位置都画成图，才算真正掌握链表的本质操作。希望这篇拆解也能帮你省下走弯路的时间。