【LeetCode】19. 删除链表的倒数第 N 个结点(中等)——代码随想录算法训练营Day04

题目链接:19. 删除链表的倒数第 N 个结点

题目描述

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

进阶:你能尝试使用一趟扫描实现吗?

文章讲解:代码随想录

视频讲解:链表遍历学清楚! | LeetCode:19.删除链表倒数第N个节点_哔哩哔哩_bilibili

题解1:暴力法

思路:先遍历一遍链表得出链表总长度,再通过计算删除链表倒数第 n 个节点。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    // 第1次遍历,得出链表元素的个数
    let size = 0;
    let cur = head;
    while (cur) {
        size++;
        cur = cur.next;
    }


    // 链表中元素的位置为0,1,2,...,size -1
    // 倒数第1个元素位置为 size -1,倒数第2个为 size - 2,倒数第 n 个为 size - n
    // 要取 size - n - 1 位置的元素,需要取头指针向后移动 size - n - 1 位
    const vHead = new ListNode(0, head); // 虚拟头节点
    cur = vHead;
    for (let i = 0; i < size - n; i++) {
        cur = cur.next;
    }
    // 删除 cur 位置的下一个元素
    cur.next = cur.next ? cur.next.next : null;
    return vHead.next;
};

分析:遍历了2次链表,时间复杂度为 O(n),空间复杂度为 O(1)。

题解2:快慢指针

思路:可以使用快慢指针的思想来解这道题。初始化时让快指针和慢指针都指向头节点,先让快指针前进 n 步,再让快指针和慢指针同时前进,当快指针到达链表结束时,慢指针就指向了倒数第 n 个节点。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    const vHead = new ListNode(0, head); // 虚拟头节点
    let slow = fast = vHead; // 初始化快慢指针
    // 快指针先前进 n + 1 步
    for (let i = 0; i < n + 1; i++) {
        fast = fast.next;
    }
    // 快慢指针同步移动,当快指针移动到链表末尾时,慢指针指向倒数第 n 个元素的上一个元素
    while (fast) {
        fast = fast.next;
        slow = slow.next;
    }
    // 删除慢指针位置的下一个元素
    slow.next = slow.next.next;
    return vHead.next;
};

分析:使用了快慢指针法,只对链表进行了一次遍历,时间复杂度为 O(n),空间复杂度为 O(1)。

收获

学会了一种非常巧妙的快慢指针思路,虽然单链表无法像数组一样可以通过下标索引直接找到对应元素,但利用快慢指针之间的差值寻找倒数元素这种方法还是很精妙的。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/317589.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

第133期 为什么一些场景下Oracle很难被替换掉(20240113)

数据库管理133期 2024-01-13 第133期 为什么一些场景下Oracle很难被替换掉&#xff08;20240113&#xff09;1 数据量2 架构3 应用改造4 Exadata和融合数据库总结 第133期 为什么一些场景下Oracle很难被替换掉&#xff08;20240113&#xff09; 今天在薛首席的群里&#xff0c…

HCIP-1

一、网络类型&#xff1a; 点到点 BMA&#xff1a;广播型多路访问 – 在一个MA网络中同时存在广播&#xff08;洪泛&#xff09;机制 NBMA&#xff1a;非广播型多路访问—在一个MA网络中&#xff0c;没有洪泛机制 MA&#xff1a;多路访问 在一个网段内&#xff0c;存在的节…

day-08 构造限制重复的字符串

思路 首先统计每个字符的个数&#xff0c;然后从后向前按照题意添加字符 解题方法 从后向前添加字符&#xff1a;1.当前字符个数<repeatLimit,直接添加 2.当前字符个数>repeatLimit,添加repeatLimit个&#xff0c;然后插入一个下一级字符 时间复杂度:O(n) 空间复杂度:…

java中多线程

文章目录 多线程进程和线程进程线程 继承Thread类方式实现多线程设置线程名字的两个方式获取正在运行的线程线程调度模型和线程优先级设置两种调度模型优先级设置 线程控制sleepjoin守护线程 线程生命周期 多线程 进程和线程 进程 进程&#xff1a;是正在运行的程序 是系统进…

【算法每日一练]-dfs (保姆级教程 篇9) #俄罗斯方块 #ABC Puzzle #lnc的工资

目录 今日知识点&#xff1a; 二维图形的状态压缩&#xff0c;存下所有的合法状态然后暴力遍历 dfs的优化剪枝 二项式定理 俄罗斯方块 ABC Puzzle lnc的工资 俄罗斯方块 322D 题意&#xff1a;在4*4方格中分别给出3个俄罗斯方块&#xff0c;问是否可以经过旋转&#xf…

TOP刊竟一个月有结果,连中两篇,感觉投了就要!简直性价比天花板!

CEJ 期刊评说 网 友 辣 评 评说1&#xff1a;审稿很快&#xff0c;编辑应该就给审稿人20天审稿&#xff0c;投过两次都特别快&#xff01; 评说2&#xff1a;确实是性价比天花板&#xff0c;文章连续被老牌的一、二、三区期刊拒&#xff0c;多亏了 CEJ把我捞了起来&#xf…

IPv6组播技术--MLDv2

MPLDv1工作机制 IPv6组播网络中RouterA和RouterB连接主机网段,在主机网段上有HostA、HostB、HostC三个接收者。假设HostA和HostB想要接收发往组播组G1的数据,HostC想要接收发往组播组G2的数据。 查询器选举机制 当一个网段内有多台IPv6组播路由器时,由于它们都可以接收到…

mysql进阶 - 存储过程

目录 1. 用途&#xff1a; 2. 相关语法 2.1 创建 2.1.1 语法 2.1.2 示例 2.2 查看存储过程 2.3 调用 2.4 修改存储过程 2.5 删除存储过程 1. 用途&#xff1a; 存储过程广泛存在于一些遗留系统&#xff0c;可以减少代码的编写。而近些年&#xff0c;存储过程很少再用…

论文阅读_训练大模型用于角色扮演

英文名称: Character-LLM: A Trainable Agent for Role-Playing 中文名称: 角色-LLM&#xff1a;训练Agent用于角色扮演 文章: [https://arxiv.org/abs/2310.10158](https://arxiv.org/abs/2310.10158) 作者: Yunfan Shao, Linyang Li, Junqi Dai, Xipeng Qiu 机构: 复旦大学…

制作 Kali 可启动 USB 驱动器

Kali USB驱动器&#xff0c;轻松安全&#xff0c;获取最新镜像&#xff0c;开始强大的安全测试&#xff01; Kali 可启动 USB 驱动器的优点&#xff1a; 不会更改主机系统的硬盘驱动器或已安装的操作系统&#xff0c;并且要返回正常操作&#xff0c;您只需删除“Kali Live”U…

31 树的存储结构二

DIsplay() 递归显示 :图示 求树的高度时&#xff0c;递归的技巧 在递归的过程中&#xff1a;ret单独和任意一个子树的子高度比较&#xff0c;如果ret<max&#xff0c;retmax ------------- 注意&#xff1a;组织链表和子链表的【元素类型】都是TLNode* 链表都要先通过TLNod…

HTB-SAU

信息收集 # cat port.nmap # Nmap 7.94 scan initiated Thu Jan 11 19:26:51 2024 as: nmap -sS --min-rate 10000 -p- -oN port.nmap 10.10.11.224 Nmap scan report for 10.10.11.224 (10.10.11.224) Host is up (0.28s latency). Not shown: 65531 closed tcp ports (r…

pymssql 报错误解决办法:20002, severity 9

错误 解决办法 python3.6&#xff0c;安装pymssql低版本&#xff08;pymssql-2.1.5-cp36-cp36m-win32.whl&#xff09;

Feature Fusion for Online Mutual KD

paper&#xff1a;Feature Fusion for Online Mutual Knowledge Distillation official implementation&#xff1a;https://github.com/Jangho-Kim/FFL-pytorch 本文的创新点 本文提出了一个名为特征融合学习&#xff08;Feature Fusion Learning, FFL&#xff09;的框架&…

流量预测中文文献阅读(郭郭专用)

目录 基于流量预测的超密集网络资源分配策略研究_2023_高雪亮_内蒙古大学&#xff08;1&#xff09;内容总结&#xff08;2&#xff09;流量预测部分1、数据集2、结果对其中的一个网格的CDR进行预测RMSE和R2近邻数据和周期数据对RMSE的影响 &#xff08;3&#xff09;基于流量预…

点餐新体验:老板自研扫码点餐小程序的成果

为了提高餐厅的效率和顾客的用餐体验&#xff0c;餐饮店老板们纷纷开始探索新的技术手段。其中&#xff0c;扫码点餐小程序就是一种非常受欢迎的解决方案。 扫码点餐小程序是一种基于微信小程序开发的餐饮点餐系统&#xff0c;它通过扫描桌码或菜品二维码&#xff0c;实现快速点…

ElasticSearch概述+SpringBoot 集成 ES

ES概述 开源的、高扩展的、分布式全文检索引擎【站内搜索】 解决问题 1.搜索词是一个整体时&#xff0c;不能拆分&#xff08;mysql整体连续&#xff09; 2.效率会低&#xff0c;不会用到索引&#xff08;mysql索引失效&#xff09; 解决方式 进行数据的存储&#xff08;只存储…

【面试宝典】图解ARP协议、TCP协议、UDP协议

一、ARP协议 二、TCP协议 三、UDP协议 四、TCP和UDP的区别

基于Springboot+uniapp的美容美发预约、会员管理、充值小程序(有文档、Java毕业设计)

大家好&#xff0c;我是DeBug&#xff0c;很高兴你能来阅读&#xff01;作为一名热爱编程的程序员&#xff0c;我希望通过这些教学笔记与大家分享我的编程经验和知识。在这里&#xff0c;我将会结合实际项目经验&#xff0c;分享编程技巧、最佳实践以及解决问题的方法。无论你是…

【LabVIEW FPGA入门】LabVIEW FPGA 实现SPI通信协议

该实现由两个组件组成&#xff1a;在 LabVIEW FPGA 中实现的 SPI 协议以及用于从主机 PC 或实时控制器与 FPGA 进行通信的 LabVIEW 主机接口。该架构允许从单个主机程序控制多个 SPI 端口&#xff0c;同时仍然允许定制 FPGA VI 以进行其他数据采集和处理。该实现不使用任何DMA&…