菏泽市网站建设_网站建设公司_版式布局_seo优化

Java版LeetCode热题100之「删除链表的倒数第 N 个结点」详解

本文约9200字，全面深入剖析 LeetCode 第19题《删除链表的倒数第 N 个结点》。涵盖题目解析、三种解法（计算长度法、栈法、双指针法）、复杂度分析、面试高频问答、实际开发应用场景、相关题目推荐等，助你彻底掌握链表操作核心技巧。

一、原题回顾

题目描述：
给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1 输出：[]

示例 3：

输入：head = [1,2], n = 1 输出：[1]

提示：

• 链表中结点的数目为sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

进阶要求：
你能尝试使用一趟扫描实现吗？

二、原题分析

这道题的核心在于：如何在不知道链表总长度的前提下，精准定位并删除倒数第n个节点？

链表是一种单向线性结构，不支持随机访问。我们无法像数组那样通过下标直接跳转到目标位置。因此，要删除某个节点，必须先找到它的前驱节点，然后修改其next指针。

但问题在于：

• 如果从前往后遍历，我们不知道“倒数第 n 个”对应的是正数第几个；
• 如果从后往前，链表没有反向指针（除非是双向链表）；
• 特别地，当要删除的是头节点时，处理逻辑与其他节点不同，容易出错。

因此，本题考察的是对链表操作的熟练度、边界条件处理能力，以及对“双指针”、“哑节点”等技巧的掌握。

三、答案构思

思路1：两次遍历（先求长度）

最直观的方法：先遍历一次链表，得到总长度L；再遍历一次，走到第L - n个节点（即目标节点的前驱），执行删除。

✅ 优点：逻辑清晰，易于理解
❌ 缺点：需要两次遍历，不符合“一趟扫描”的进阶要求

思路2：使用栈（辅助空间）

遍历链表，将所有节点压入栈。由于栈是 LIFO（后进先出），弹出n次后，栈顶就是目标节点的前驱。

✅ 优点：天然支持“倒序访问”
❌ 缺点：额外 O(L) 空间，且仍需完整遍历一次

思路3：双指针（快慢指针）

这是最优解！

• 使用两个指针first和second，初始都指向头节点（或哑节点）；
• 先让first向前走n步；
• 然后first和second同步前进，直到first到达末尾；
• 此时second恰好位于倒数第n+1个节点（即目标节点的前驱）。

✅ 优点：仅需一趟扫描 + O(1) 空间，完美满足进阶要求！

📌关键技巧：引入“哑节点（Dummy Node）”
为了避免单独处理“删除头节点”的特殊情况，我们在原链表前加一个虚拟头节点（dummy），其next指向原head。这样，无论删除哪个节点，操作逻辑都统一为“修改前驱的 next 指针”。

四、完整答案（Java 实现）

下面分别给出三种方法的完整 Java 代码。

方法一：计算链表长度（两次遍历）

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){// 创建哑节点，简化边界处理ListNodedummy=newListNode(0,head);// 第一次遍历：获取链表长度intlength=getLength(head);// 第二次遍历：找到倒数第 n 个节点的前驱ListNodecur=dummy;for(inti=1;i<length-n+1;i++){cur=cur.next;}// 执行删除操作cur.next=cur.next.next;// 返回新头节点returndummy.next;}privateintgetLength(ListNodehead){intlength=0;while(head!=null){length++;head=head.next;}returnlength;}}

方法二：栈（辅助空间）

importjava.util.Deque;importjava.util.LinkedList;classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodedummy=newListNode(0,head);Deque<ListNode>stack=newLinkedList<>();ListNodecur=dummy;// 将所有节点（包括 dummy）压入栈while(cur!=null){stack.push(cur);cur=cur.next;}// 弹出 n 个节点，此时栈顶即为前驱节点for(inti=0;i<n;i++){stack.pop();}ListNodeprev=stack.peek();prev.next=prev.next.next;returndummy.next;}}

方法三：双指针（推荐！一趟扫描）

classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){// 哑节点：统一删除逻辑ListNodedummy=newListNode(0,head);// first 指向原 head，second 指向 dummyListNodefirst=head;ListNodesecond=dummy;// first 先走 n 步for(inti=0;i<n;i++){first=first.next;}// first 和 second 同步前进，直到 first 到达末尾while(first!=null){first=first.next;second=second.next;}// 此时 second 指向目标节点的前驱second.next=second.next.next;returndummy.next;}}

✅强烈推荐使用方法三：时间效率高、空间占用少、代码简洁、符合进阶要求。

五、代码分析

1. 哑节点（Dummy Node）的作用

• 问题：若要删除头节点（如[1,2,3], n=3），常规方法需特殊判断if (n == length)。
• 解决方案：引入dummy节点，使原head成为dummy.next。
• 效果：所有删除操作都变为“修改前驱节点的 next 指针”，无需区分是否为头节点。

ListNodedummy=newListNode(0,head);// ...returndummy.next;// 返回真正的头节点

2. 双指针的移动逻辑

• first先走n步 → 此时first与second相距n个节点；
• 同步移动 → 当first == null（即走过整个链表），second恰好在倒数第n+1位；
• 举例：[1,2,3,4,5], n=2
  • 初始：first=1,second=dummy(→1)
  • first走2步：first=3
  • 同步移动：first=4→5→null，second=1→2→3
  • 此时second=3，second.next=4（即要删除的节点）

3. 边界条件处理

• n == 1：删除尾节点 →second停在倒数第二个节点，next = null
• n == sz：删除头节点 →second停在dummy，dummy.next = head.next
• 链表只有一个节点 → 删除后返回null

所有情况均被dummy机制优雅处理。

六、时间复杂度和空间复杂度分析

其中L为链表长度。

• 双指针法最优：既满足时间效率，又节省空间，且仅需一次遍历。
• 栈法虽然是一趟扫描，但空间开销大，不适合内存敏感场景。
• 计算长度法逻辑简单，但在性能要求高的场景不推荐。

七、常见问题解答（FAQ）

Q1：为什么不能直接让second指向head，而要指向dummy？

答：如果second指向head，当n = L（删除头节点）时，second最终会停在head，但我们无法获取head的前驱（因为不存在）。而dummy作为虚拟前驱，解决了这一问题。

Q2：双指针中，first先走n步还是n-1步？

答：必须走n步。
目标是让second停在目标节点的前驱。
若first走n-1步，则second会停在目标节点本身，无法完成删除（缺少前驱指针）。

Q3：是否需要释放被删除节点的内存？

答：在 Java 中，内存由 GC 自动管理，无需手动释放。但在 C/C++ 等语言中，应显式free或delete被删除节点，避免内存泄漏。面试时应主动与面试官确认。

Q4：如果n大于链表长度怎么办？

答：题目已保证1 <= n <= sz，无需处理非法输入。但在实际工程中，应加入校验逻辑。

八、优化思路

1. 提前终止（剪枝）

在双指针法中，若first在走n步时提前变为null，说明n == L，可直接返回head.next。但此优化意义不大，因题目保证n <= L。

2. 递归解法（不推荐）

可通过递归实现“从后往前计数”，但空间复杂度为 O(L)（递归栈），且代码复杂，不实用。

3. 工程化改进

• 添加输入校验：if (head == null || n <= 0) return head;
• 日志记录：便于调试
• 单元测试覆盖所有边界 case

九、数据结构与算法基础知识点回顾

1. 链表（Linked List）

• 特点：动态大小、非连续内存、通过指针连接
• 类型：单向、双向、循环
• 操作：插入、删除 O(1)（已知位置），查找 O(n)

2. 哑节点（Dummy/Sentinel Node）

• 作用：简化边界处理，统一操作逻辑
• 应用场景：链表合并、反转、删除等

3. 双指针（Two Pointers）

• 快慢指针：检测环、找中点、本题
• 滑动窗口：子数组/子串问题
• 对撞指针：两数之和、回文判断

4. 栈（Stack）

• LIFO：后进先出
• 应用：括号匹配、表达式求值、倒序访问

十、面试官提问环节（模拟）

❓ 问题1：你能解释一下为什么双指针法只需要一趟扫描吗？

回答：
是的。我们让first指针先走n步，建立一个固定长度为n的“窗口”。随后first和second同步移动，当first到达末尾时，second自然就落在了倒数第n+1个位置。整个过程只遍历了链表一次，时间复杂度 O(L)。

❓ 问题2：如果链表非常长（比如10亿节点），你的解法还适用吗？

回答：
双指针法依然适用。因为它只使用两个指针和常数额外空间，不会因链表长度增加而消耗更多内存。相比之下，栈法会因递归深度或栈空间不足而崩溃。因此双指针是工业级推荐方案。

❓ 问题3：如何扩展这个问题？比如删除倒数第 n 到 m 个节点？

回答：
可以先用双指针找到倒数第m个节点的前驱，再找到倒数第n个节点，然后一次性断开连接。或者先计算长度，再确定正向位置区间进行删除。核心仍是定位前驱节点。

❓ 问题4：你在代码中用了 dummy 节点，这是什么设计模式？

回答：
这不是严格意义上的设计模式，而是一种编程技巧，常被称为“哨兵节点”或“虚拟头节点”。它在算法题和系统设计中广泛用于消除边界条件的特殊处理，提升代码健壮性和可读性。

十一、这道算法题在实际开发中的应用

虽然“删除倒数第 n 个节点”看似是一个玩具问题，但其背后的思想在实际开发中非常有用：

1.日志系统中的滑动窗口

• 保留最近 N 条日志，超出则删除最旧的（相当于“删除倒数第 N+1 个”）
• 可用双指针维护窗口边界

2.缓存淘汰策略（如 LRU 的简化版）

• 当缓存满时，移除最早访问的项（若用链表实现，可能涉及尾部删除）

3.消息队列的截断操作

• 限制队列最大长度，自动丢弃旧消息

4.链表操作的通用模板

• “找前驱 + 修改指针”是链表删除的标准范式
• 哑节点技巧可复用于链表合并、排序等场景

💡核心价值：训练对指针操作和边界条件的敏感度，这是编写健壮系统代码的基础。

十二、相关题目推荐

掌握本题后，可挑战以下 LeetCode 题目：

建议按顺序练习，逐步提升链表操作能力。

十三、总结与延伸

✅ 本题核心收获

1. 链表删除的本质：必须通过前驱节点修改next指针；
2. 哑节点的价值：消除头节点删除的特殊 case，提升代码鲁棒性；
3. 双指针的威力：用 O(1) 空间实现“倒序定位”，是链表题的黄金技巧；
4. 一趟扫描的意义：在流式数据或大数据场景下，减少 I/O 次数至关重要。

🔮 延伸思考

• 如果链表是双向的？
  可直接从尾部向前走n-1步，但空间开销更大（每个节点多一个指针）。

• 如果要求返回被删除节点的值？
  在删除前保存second.next.val即可。

• 能否用递归实现？
  可以，通过递归回溯时计数，但空间复杂度 O(L)，不推荐。

🌟 最后建议

• 手写代码：务必在白板或纸上手写双指针解法，确保无 bug；
• 讲清思路：面试时先说“我打算用双指针 + 哑节点”，再写代码；
• 测试用例：主动提出测试[1], n=1和[1,2], n=2等边界 case。

“链表题，指针是灵魂，边界是魔鬼。”
掌握本题，你就迈出了征服链表面试题的第一步。继续加油！