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

简介: LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)



一、编程题: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;
        }
    }
}

提交结果:


总结

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

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

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

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


相关文章
|
2天前
|
算法
"刷题记录:哈希表+双指针 | leetcode-2465. 不同的平均值数目 "
该文段是一篇关于编程题目的解答,主要讨论如何找到数组中所有不同平均值的个数。作者首先使用排序和哈希集来解决,将数组转为列表排序后,通过双指针计算平均值并存入哈希集以去重。然后,作者发现可以优化方案,通过双指针在排序后的数组中直接计算两数之和,用哈希集记录不重复的和,从而避免实际计算平均值,提高了算法效率。最终代码展示了这两种方法。
10 0
|
3天前
|
索引
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
8 0
|
3天前
|
存储 算法 索引
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
13 1
|
3天前
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
9 0
|
3天前
|
索引
【力扣刷题】两数求和、移动零、相交链表、反转链表
【力扣刷题】两数求和、移动零、相交链表、反转链表
11 2
【力扣刷题】两数求和、移动零、相交链表、反转链表
|
3天前
|
索引
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
7 0
|
3天前
|
索引
【力扣刷题】回文链表、环形链表、合并两个有序链表
【力扣刷题】回文链表、环形链表、合并两个有序链表
9 0
|
5天前
|
算法 索引
力扣刷题【第一期】
这是一个关于算法的总结,包含7个不同的问题。1)爬楼梯问题,使用动态规划,通过迭代找到到达n阶楼梯的不同方法数。2)两数之和,通过双重循环找出数组中和为目标值的两个数的索引。3)移动零,使用双指针将数组中的0移到末尾。4)合并有序链表,创建新链表按升序合并两个链表。5)删除链表重复值,遍历链表删除重复元素。6)环形链表检测,使用快慢指针判断链表是否有环。7)相交链表,计算链表长度找
10 1
|
6天前
|
存储 Java
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
12 0
|
15天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
14 0