算法初学者解决删除链表倒数的节点(力扣19题)(双指针)

发布时间：2026/7/7 13:50:44

1，📚题目介绍

在开始之前请理解下图1

(仅仅在本题的话，链表节点的值不重要，所以我的图省去了值)

题目要求，删除倒数第n个节点。

同时链表至少有一个节点

n在链表节点数之内

2，💡采用方法

这里我采用的是双指针法，至于为什么我也解释不清，先用就行了。

3，🤔具体逻辑

所谓快慢指针，肯定要一个快指针和慢指针了。

定义在哪里呢？先在head节点定义这两位吧。

然后！请集中注意力，争取看一遍就理解.

想删除倒数第一个节点，就必须要找到倒数第二个节点。

想删除倒数第二个节点，就必须要找到倒数第三个节点。

（这是链表删除的知识，如果不懂建议了解一下链表删除操作）

请记住点①：想删除倒数第n个节点，就要找到倒数第n+1个节点。

（你可能想到了极限情况，链表只有一个节点，但先忽略，后面再提）

然后，是让人头疼的问题，单向链表，如何找到最后一个节点？

这不简单吗！循环一下不就行了？这样确实可以，而题目鼓励我们用一次循环就搞定，这里我就用第一次循环的思路。

想找到最后一个节点，最容易想到的方法就是遍历，那就这样做，但是呢，找到最后一个节点的同时顺便把倒数第n+1个节点找到，这样就能删了。

请记住点②：快指针找最后一个节点，慢指针找倒数第n+1个节点

(依据点①,找到倒数第n+1个就可以删除第n个节点)

这时候，你就会神奇的发现，快慢指针的距离，神奇的差了n个节点！

如下图，想删除倒数第2个节点，就让slow与fast差了两个节点，也就是让快指针提前慢指针走2步！

请记住点③：快指针需要提前慢指针n步

综上，想要删除第n个节点就要让先快指针领先慢指针n个节点！

这样似乎就可以写出代码了

定义快慢指针于head
让快指针提前走n步
快慢一起遍历，直到快指针找到了最后一个节点（此时，慢指针就找到了倒数n+1个节点，就能删除倒数第n个节点了！这是题目要求的啊，不要忘记题目的要求）
删除第n个节点
返回头结点

但是这样写的话，就会发现是通过不了的。

肯定是遗漏了什么东西，没错，就是极限情况：删除的是链表的头结点，此时模拟一下

按照之前的思路，要删除倒数第n个节点，就要让fast指针领先slow指针一步，由于slow本身就在头结点上，根本找不到头结点前面的节点，这怎么删除呢？

这时候，就要引入传说中的虚拟头结点(dummy head)了，也不要被吓到，这就是一个新的节点，你到时候new ListNode一下就行了，只是他的名字叫虚拟头结点

这个虚拟头结点的一个好处就是方便这种头结点的处理

处理如下图

现在你再看看呢？fast领先慢指针1步，这时fast指针不就是最后一个头结点吗？slow指针不就是倒数第n+1(这个例子中n=1也就是1+1=2)个节点吗?

找到倒数第n+1个(倒数第2个)也就是能正确删除倒数第n(倒数第1个)个节点了。

这就是引入虚拟头结点的好处。

4，⚛️题解

这样本题两个问题，一个主题逻辑和一个极限情况的坑就解决了。

写出如下代码(java)：

class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { //定义虚拟头结点用于解决链表只有一个节点的情况 ListNode dummyHead=new ListNode(); //保存头节点 dummyHead.next=head; //在dummyhead上定义快慢指针 ListNode fast=dummyHead; ListNode slow=dummyHead; //让快指针领先n步 while(n-->0){ fast=fast.next; } //一起移动，找到最后的节点 while(fast.next!=null){ fast=fast.next; slow=slow.next; } //删除操作 slow.next=slow.next.next; //返回题目要求的头结点 return dummyHead.next; } }