【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点

简介: 【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点

题目

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

输入: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 个结点,并且返回链表的头结点。 
//
// 
//
// 示例 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 
// 
//
// 
//
// 进阶:你能尝试使用一趟扫描实现吗? 
//
// Related Topics 链表 双指针 👍 2822 👎 0
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        /**
         * 首先找倒数第k个节点
         * 然后删除
         */
        //虚拟头节点
        ListNode dummy=new ListNode();
        dummy.next=head;//把虚拟头节点放在前面
        //找到倒数第N个节点
        ListNode x=findFromEnd(dummy,n+1);//n+1代表长度
        //删掉倒数第n个节点
        x.next=x.next.next;
        return dummy.next;
    }
    //查找倒数第K个节点的位置
    ListNode findFromEnd(ListNode head,int k){
        ListNode p1=head;
        //p1先走k步
        for (int i=0;i<k;i++){
            p1=p1.next;
        }
        ListNode p2=head;
        //p1和p2同时走n-k步,p2停留的就是倒数第k步
        while (p1!=null){
            p2=p2.next;
            p1=p1.next;
        }
        return p2;
    }
}
//leetcode submit region end(Prohibit modification and deletion)


目录
相关文章
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
存储 算法 搜索推荐
链表的中间结点
【10月更文挑战第24天】链表的中间结点是链表操作中的一个重要概念,通过快慢指针法等方法可以高效地找到它。中间结点在数据分割、平衡检测、算法应用等方面都有着重要的意义。在实际编程中,理解和掌握寻找中间结点的方法对于解决链表相关问题具有重要价值。
15 1
|
2月前
|
存储 缓存 算法
经典算法之链表篇(三)
经典算法之链表篇(三)
|
2月前
|
算法
经典算法之链表篇(二)
经典算法之链表篇(二)
|
2月前
|
算法 索引
经典算法之链表篇
经典算法之链表篇
|
2月前
|
算法 API 计算机视觉
人脸识别笔记(一):通过yuface调包(参数量54K更快更小更准的算法) 来实现人脸识别
本文介绍了YuNet系列人脸检测算法的优化和使用,包括YuNet-s和YuNet-n,以及通过yuface库和onnx在不同场景下实现人脸检测的方法。
62 1
|
2月前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
69 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
2月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
52 0
|
2月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
17 0