当前位置：首页 > news >正文

【LeetCode 刷题日】19.删除链表的倒数第n个节点

news 2026/6/22 22:41:48

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者评论和@
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：
继续对链表的学习，暴打LeetCode，接下来就快到了哈希表，其实我在写这些算法之前，看过一些关于数据结构的书，有的书上来就是摆一堆源码，看的迷迷糊糊的，有的又太过于简单了，目前还没找到很合适的书，有没有大佬有推荐的，以及一些计算机基础四大件的数据。

题目背景：LeetCode19

给你一个链表，删除链表的倒数第 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]

题目答案：

class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { //新建一个虚拟头节点指向head ListNode dummyNode = new ListNode(0); dummyNode.next = head; //快慢指针指向虚拟头节点 ListNode fastIndex = dummyNode; ListNode slowIndex = dummyNode; // 只要快慢指针相差 n 个结点即可 for (int i = 0; i <= n; i++) { fastIndex = fastIndex.next; } while (fastIndex != null) { fastIndex = fastIndex.next; slowIndex = slowIndex.next; } // 此时 slowIndex 的位置就是待删除元素的前一个位置。 // 具体情况可自己画一个链表长度为 3 的图来模拟代码来理解 // 检查 slowIndex.next 是否为 null，以避免空指针异常 if (slowIndex.next != null) { slowIndex.next = slowIndex.next.next; } return dummyNode.next; } }

题目解析：

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。思路是这样的，但要注意一些细节。

这时就有同学不理解，为什么快指针要先走n步，当然快指针肯定是比慢指针快的，从名字就看出来了，但具体原理是什么呢？

简单的来说：先走n步，就是为了制造快慢指针之间的间距，那为什么要制造间距呢，首先要明确题目要干嘛，要删除倒数第n个节点，根据链表的特性，我们删除一个节点必须要知道这个节点的前驱节点，所以我们做的一切都是为了让慢指针最后停在要删除节点的前置节点那个位置。这样才能slow.next = slow.next.next删掉目标节点。

因此我们看流程：

图解：为什么快指针要先走 n 步？
举个最清晰的例子：链表：1 → 2 → 3 → 4 → 5，n = 2要删除：倒数第 2 个节点 4
初始状态
plaintext
fast slow ↓ 1 → 2 → 3 → 4 → 5 → null
① 快指针先走 n 步（n=2，走 2 步）
plaintext
fast slow ↓ ↓ 1 → 2 → 3 → 4 → 5 → null
👉此时快慢相差 n 个节点
② 快慢一起走，直到 fast 到末尾
plaintext
fast slow ↓ ↓ 1 → 2 → 3 → 4 → 5 → null
👉slow 正好停在 3，是 4 的前一个！
③ 删除
plaintext
slow.next = slow.next.next
结果：1 → 2 → 3 → 5 → null