LeetCode刷题---19. 删除链表的倒数第 N 个结点（双指针-快慢指针）

• 💌 所属专栏：【LeetCode题解（持续更新中）】

• 😀 作  者：我是夜阑的狗🐶

• 🚀 个人简介：一个正在努力学技术的码仔，专注基础和实战分享 ，欢迎咨询！

• 💖 欢迎大家：这里是CSDN，我总结知识的地方，喜欢的话请三连，有问题请私信 😘 😘 😘
  
  

您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！🤩 🤩 🤩

---

前言

  大家好，又见面了，我是夜阑的狗，本文是专栏【LeetCode题解】专栏的第15篇文章，主要讲解是LeetCode19. 删除链表的倒数第 N 个结点（双指针-快慢指针）。
  专栏地址：【LeetCode题解（持续更新中）】， 此专栏是我是夜阑的狗对LeetCode问题的讲解，希望能够加深自己的印象，以及帮助到其他的小伙伴😉😉。
  如果文章有什么需要改进的地方还请大佬不吝赐教👏👏。

---

一、编程题：19. 删除链表的倒数第 N 个结点（双指针-快慢指针）

1.题目描述

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

2.示例1：

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

3.示例2：

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

4.示例3：

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

5.提示：

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

6.进阶：

• 你能尝试使用一趟扫描实现吗？

---

二、解题思路

  可以根据滑动窗口的思想来解决本题；
  这题采用双指针，本题主要关键点为：

• 1.该怎么去移动这两个指针？这一点要理清楚。这里双指针移动就比较简单了，分别向下移动一步即可；

1.思路

解决方法1（个人想法）：

快慢指针第一次相遇：

• Step 1.创建指针fast和slow均指向head，首先要先找到快指针fast的位置，fast与slow之间间隔n-1个节点;
• Step 2.同时使用fast和slow对链表进行遍历，直到fast或者fast.next为空;
• Step 3.当fast==null时，找了倒数第n+1个节点，此时slow的下一个节点就是要删除的节点；
• Step 4.当fast.next==null时，找了倒数第n个节点（也就是头节点），将head向下即可;

看不懂解释的话，直接看算法图解比较容易理解点

2.复杂度分析：

时间复杂度：O(L)，其中L是链表的长度。
空间复杂度：O(1)

3.算法图解

红色部分代表快指针fast，灰色部分代表慢指针slow（注：本人不会做成流程动画，希望会的朋友可以私信我指点一二，说个软件名字也可以，谢谢）

---

三、代码实现

每个代码块都写了注释，方便理解，代码还可以改进；

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head, slow = head;
        //先找出快指针的位置
        for(int i = 0; i < n; i++) fast = fast.next;
        
        while(true){
            if(fast == null)return head = head.next;
            else if(fast.next == null){
                slow.next = slow.next.next;
                return head;
            }
            //同时移动两个指针
            slow = slow.next;
            fast = fast.next;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

提交结果：

---

总结

以上就是今天要讲的内容，做题的时候发现寻找倒数第n个节点并删除，由于是单链表，所以需要找到倒数第n个节点的前驱结点才能删除，这样就可以把问题转变为寻找倒数第n个节点了，在利用滑动窗口的思路来移动快慢指针就可以了，所以就赶紧记录一下这时刻。

感谢观看，如果有帮助到你，请给题解点个赞和收藏，让更多的人看到。🌹 🌹 🌹

也欢迎你，关注我。👍 👍 👍

原创不易，还希望各位大佬支持一下，你们的点赞、收藏和留言对我真的很重要！！！💕 💕 💕 最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

更多专栏订阅:

• 😀 【LeetCode题解（持续更新中）】
• 🚝 【Java Web项目构建过程】
• 💛 【数字图像处理】
• ⚽ 【JavaScript随手笔记】
• 🤩 【大数据学习笔记（华为云）】
• 🦄 【程序错误解决方法（建议收藏）】
• 🚀 【软件安装教程】

订阅更多，你们将会看到更多的优质内容！！