力扣经典题目解析--删除链表的倒数第 N 个结点

原题地址:. - 力扣(LeetCode)

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

示例 1:

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

示例 2:

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

解析

在链表中删除某个节点,其实就是将之前一个节点next,直接指向当前节点的后一个节点,相当于“跳过”了这个节点。

计算链表长度(二次遍历)

最简单的想法是,我们首先从头节点开始对链表进行一次遍历,得到链表的长度 L。

然后,我们再从头节点开始对链表进行一次遍历,当遍历到第 L-N+1 个节点时,它就是我们需要删除的倒数第N个节点。

这样,总共做两次遍历,我们就可以得到结果。

public ListNode removeNthFromEnd(ListNode head, int n) {
    int length = 0;
    ListNode cur = head;
    while (cur != null) {
        length++;
        cur = cur.next;
    }
    ListNode sentinel = new ListNode(-1, head);
    cur = sentinel;
    for (int i = 0; i < length - n; i++) {
        cur = cur.next;
    }
    cur.next = cur.next.next;
    return sentinel.next;
}

双指针

我们可以使用两个指针 first 和 second 同时对链表进行遍历,要求 first 比 second 超前 N 个节点。

这样,它们总是保持着N的距离,当 first 遍历到链表的末尾(null)时,second 就恰好处于第L-N+1,也就是倒数第 N 个节点了。

public ListNode removeNthFromEnd1(ListNode head, int n) {
    ListNode sentinel = new ListNode(-1, head);
    ListNode first = sentinel;
    ListNode second = head;
    for (int i = 0; i < n; i++) {
        second = second.next;
    }
    while (second != null) {
        first = first.next;
        second = second.next;
    }
    first.next = first.next.next;
    return sentinel.next;
}

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

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

相关文章

【韩顺平零基础学java】第12章课后题

练习题1 如果用户输入的不是一个整数&#xff0c;就提示他反复输入&#xff0c;直到输入的是一个整数为止 import java.util.Scanner;/*如果用户输入的不是一个整数&#xff0c;就反复输入&#xff0c;直到输入的是一个整数为止*/ public class TryCatchExercise04 {public s…

代码随想录算法训练营Day37 | LeetCode738.单调递增的数字、LeetCode968.监控二叉树、贪心算法总结

LeetCode738.单调递增的数字 思路&#xff1a;与分糖果的题目同理&#xff0c;因为需要与前一位数比较&#xff0c;并且修改这两个数&#xff0c;因此需要从后往前遍历&#xff0c;当前一位数比当前数大时&#xff0c;则前一个数-1&#xff0c;后一个数变为9。 代码细节&…

金三银四,程序员如何备战面试季

金三银四&#xff0c;程序员如何备战面试季 一个人简介二前言三面试技巧分享3.1 自我介绍 四技术问题回答4.1 团队协作经验展示 五职业规划建议5.1 短期目标5.2 中长期目标 六后记 一个人简介 &#x1f3d8;️&#x1f3d8;️个人主页&#xff1a;以山河作礼。 &#x1f396;️…

【数据存储】大端存储||小端存储(超详细解析,小白一看就懂!!!)

目录 一、前言 二、什么是低地址、高地址 &#xff1f; 三、什么是数据的高位和低位 &#xff1f; 四、什么是大小端存储&#xff1f; &#x1f349; 小端存储详解 &#x1f352; 大端存储详解 五、为什么会有大小端存储&#xff1f; &#x1f34d;大端存储的优点 &#…

跨境电商趋势解析:社交电商携手私域流量运营,精准触达与转化

随着全球化的深入发展&#xff0c;跨境电商逐渐成为全球贸易的重要组成部分。在这一背景下&#xff0c;社交电商作为一种新兴的商业模式&#xff0c;正逐渐在跨境电商领域崭露头角&#xff0c;并对私域流量的运营产生了深远的影响。本文Nox聚星将和大家分析社交电商在跨境电商中…

数据结构(一)综述

一、常见的数据结构 数据结构优点缺点数组查找快增删慢链表增删快查找慢哈希表增删、查找都快数据散列&#xff0c;对存储空间有浪费栈顶部元素插入和取出快除顶部元素外&#xff0c;存取其他元素都很慢队列顶部元素取出和尾部元素插入快存取其他元素都很慢二叉树增删、查找都快…

交叉编译qt5.14.2

qt源码下载地址&#xff1a;qt-everywhere-src-5.14.2.tar.xz 1.修改qt-everywhere-src-5.14.2/qtbase/mkspecs/linux-arm-gnueabi-g/qmake.conf文件&#xff1a; # # qmake configuration for building with arm-linux-gnueabi-g #MAKEFILE_GENERATOR UNIX CONFIG …

Guitar Pro 8.1中文版永久许可证激活2024最新24位注册激活码生成器

Guitar Pro是一款非常受欢迎的音乐制作软件&#xff0c;它可以帮助用户创建和编辑各种音乐曲谱。从其诞生以来就送专门为了编写吉他谱而研发迭代的。 尽管这款产品可能已经成为全球最受欢迎的吉他打谱软件&#xff0c;在编写吉他六线谱和乐队总谱中始终处于行业领先地位&#…

返回静态数据

在Java项目中&#xff0c;往往不会一直返回某某数据&#xff0c;而是会返回一个静态页面&#xff0c;那么&#xff0c;如何正确返回一个静态页面呢&#xff1f;&#xff1f; 要想成功的返回一个静态页面前提是必须要有一个静态页面&#xff1a; <!DOCTYPE html> <ht…

GEE 数据集 ——利用leafmap python软件包实现NASA数据的接入(colab示例)

我们如何获取我们想要的数据,这里我们通过 leafmap python软件包实现NASA数据种全球超过9000+的数据集产品的接入和使用。这里我们使用在线的colab来实现处理,因为这里我们可以很好的应用已经在线配置好的colab环境来实现,省去了安装过程的繁琐。 要下载和访问数据,您需要…

rust学习(tokio协程分析一)

代码&#xff1a; async fn doAsyncPrint(v:u32) {println!("start doAsyncPrint,v is {},tid is {:?}",v,system::myTid());//thread::sleep(Duration::from_secs(1));time::sleep(Duration::from_secs(10)).await;println!("end,v is {},tid is {:?}"…

MacOS开发环境搭建

MacOS开发环境搭建 一、MacOS二、Python三、MacOS搭建Python开发环境1.Python下载地址1.1 Python官网地址1.2 Python下载地址 2.安装Python3.安装Python4.安装PyCharm5.创建一个Python项目6.配置PyCharm7.安装Python包8.运行Python代码9.总结 一、MacOS macOS是一套由苹果开发的…

云原生数据库 GaiaDB 支持新的管理工具啦

GaiaDB 是百度智能云自研的新一代企业级关系型数据库&#xff0c;最大容量可扩展 500TB 以上&#xff0c;吞吐达到 150 万以上 QPS。 作为一款 100% 兼容 MySQL 的云原生数据库产品&#xff0c;用户可以通过多种客户端工具连接 GaiaDB 实例&#xff0c;例如 MySQL Workbench、N…

【产品经理方法论——产品的基本概念】

1. 产品学三元素 产品学有三个元素&#xff1a;用户、需求、产品 产品学的内容&#xff1a;根据用户的需求设计产品&#xff0c;使用产品服务用户 仅仅通过三个元素无法说明每个元素的概念&#xff0c;因为三个元素互为说明关系。 通过引入人/群体来说明三个元素的关系。 需…

全局渐变滚动条样式

效果如下&#xff1a; APP.vue<style> /* 整个滚动条 */ ::-webkit-scrollbar {width: 5px;height: 10px; } /* 滚动条上的滚动滑块 */ ::-webkit-scrollbar-thumb {background-color: #49b1f5;/* 关键代码 */background-image: -webkit-linear-gradient(45deg,rgba(255,…

Svg Flow Editor 原生svg流程图编辑器(一)

效果展示 项目概述 svg flow editor 是一款流程图编辑器&#xff0c;提供了一系列流程图交互、编辑所必需的功能&#xff0c;支持前端研发自定义开发各种逻辑编排场景&#xff0c;如流程图、ER 图、BPMN 流程等。 目前也有比较好的流程图设计框架&#xff0c;但是还是难满足项目…

鸿蒙Harmony应用开发—ArkTS声明式开发(通用属性:隐私遮罩)

用于对组件内容进行隐私遮罩处理。 说明&#xff1a; 从API Version 10开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 obscured obscured(reasons: Array<ObscuredReasons>) 设置组件内容的遮罩类型。 系统能力&#xff1a; Sys…

拓尔微代理商 TMI3252T 600kHz 18V 2A同步COT降压转换器

TMI3252/S/T是高效率600kHz&#xff0c;恒定导通时间 &#xff08;COT&#xff09; 控制同步模式降压型DC-DC转换器&#xff0c;能够提供高达2A电流。TMI3252/S/T集成主要具有极低 RDS&#xff08;ON&#xff09; 的开关和同步开关以尽量减少传导损耗。低输出电压纹波和小尺寸的…

E8-写了一个方法,处理一个表单里有多组需要实现单选或复选的复选框

起因 今天同事发来需求&#xff0c;要做一个工作流&#xff0c;其中表单里有几组选项。在纸质单上是留出位置画勾选择的。简单的聊了一下对填报的要求&#xff0c;要求有的组要控制单选&#xff0c;有的组还不需要制多选。用文字来描述很晦涩&#xff0c;看到表单估计小伙伴们…

上位机图像处理和嵌入式模块部署(qmacvisual入门)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 虽然我们前面学习了很多的知识点&#xff0c;比如说在windows这边&#xff0c;用qt写界面&#xff0c;用opencv写图像处理代码&#xff1b;在linux…