【LeetCode链表#10】删除链表中倒数第n个节点(双指针)

删除链表倒数第N个节点

力扣题目链接(opens new window)

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

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

示例 1:

19.删除链表的倒数第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]

思路

最开始我是想先把链表翻转,然后遍历到第n个节点,将其删除,然后再把链表翻转并返回

这么做显然提升了代码复杂度,以至于我并没有写出逻辑正常的代码,并且我估计写出来也超时了

参考删除第n个链表节点的操作

我们可以发现:要删除某个节点,当前指针cur必须指向待删除节点的前一个节点

这样,通过将cur指向下一个节点的下一个节点就可以把待删除节点移除

明确了删除方式之后,那么如何找到倒数第n个节点?

这里需要引入双指针思想,分别定义快慢指针指向dummy

快指针fast先移动n步

然后快慢指针一起向后移动,直到快指针指向null

此时,slow指向的就是倒数第n个节点

但是根据删除节点的操作,现在的情况我们是删不了slow指向的节点的,只能删除下一个

即慢指针slow要指向待删除节点的前一个

所以快指针fast应该先走n+1步

代码
class Solution {
    
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //双指针法
        //创建dummy
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        //快慢指针指向dummy
        ListNode fast = dummy;
        ListNode slow = dummy;

        n++;//让fast走n+1步
        for(int i = n; i > 0; i--){
            if(fast == null){//避免走着走着到链表尾部的情况
                break;
            }
            fast = fast.next;
        }

        //快慢指针一起移动
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        //注意删除操作
        slow.next = slow.next.next;
        return dummy.next;

    }
}
易错点

1、为了让慢指针落在待删除节点前,快指针需要先走n+1步

并且不能写成:

for(int i = n; i > 0; i--){
            if(fast == null){//避免走着走着到链表尾部的情况
                break;
            }
            fast = fast.next;
        }
fast = fast.next;

因为如果n大于链表长度,那之后就相当于对空指针进行操作了

2、删除操作

删除操作是

slow.next = slow.next.next;//让待删除节点直接等于它之后的一个节点,即代替掉要删除的节点

而不是

slow = slow.next.next;//移动slow到它的下下一个位置
本文转载于网络 如有侵权请联系删除

相关文章

  • python入门与实战--列表

    4.1列表简介python语言中,列表(list)是个很重要的概念。列表能够将多个元素组合起来(组合是一种很重要的创新方式),每个元素用逗号隔开,可以对这些元素做统一的处理,如:>>>a=["www","cvtutorials","com"] >>>type(a) <class'list'>复制即可看到输出<class'list'>,这个输出的意思是a的类型是list(前面类型转换的时候用过type)。4.2访问列表元素可以访问列表元素应该是列表最基本的功能,你可以回想下高中时期学到的数学概念:数列,这对你理解列表元素的访问会有很大帮助。比如有个数列0,1,2,3,4,...如果我问你这个数列的第3个元素是什么?你会按顺序找到第三个元素,然后告诉我是2。“第三个元素”这个说法抽象出来就是索引,我们用索引标记数列中元素的位置。和数学中的数列不同,计算机的世界里索引大多从0开始,比如下面的列表:a=["www",

  • ROP-Ret2libc详解

    利用原理ret2libc这种攻击方式主要是针对动态链接(Dynamiclinking)编译的程序,因为正常情况下是无法在程序中找到像system()、execve()这种系统级函数.当程序开始运行时会加载系统库中的函数,通过函数返回地址直接指向系统库(libc.so.6)中的函数,如system函数,从而执行例如system函数获得shell。主要目的劫持binary执行system(/bin/sh)解题思路一般有一个溢出点时,要进行两次劫持。第一次劫持是为了泄露出某个函数的地址(需要构造两条件)控制程序eip指向,为第二次劫持做准备寻找output函数(如puts和write)和待泄露函数只能泄露使用了的函数:因为动态链接库的加载机制是lazy原则(got表)libc.so动态链接库中的函数之间相对偏移固定。每个函数的地址最低的12位并不会发生改变。(即后三位。即便开启PIE)第二次劫持是为了控制binary返回到libc执行system(bin/sh)解题步骤前骤使用ldd确认该程序所使用的本地libc库一般在打本地的程序时,都使用这个库远程时,先确定泄露出的某函数的真实地址,在利

  • 冲上市三年,米哈游终迎IPO“崩坏”

    配图来自Canva二次元游戏厂商米哈游近来面对的事情不少,先是其首款推出的女性向游戏《未定事件薄》被指碰瓷式营销。而现在米哈游推出的另一款新游戏《原神》被指“国产塞尔达”的抄袭事件,更是将米哈游推至舆论的风尖浪口。在深陷舆论的同时,米哈游苦等了三年的IPO也宣告终止,无缘“二次元文化第一股”。“崩坏”系列难撑IPO米哈游靠着二次元游戏IP“崩坏”系列在游戏行业里大杀特杀,斩获颇丰。不过凭借着“崩坏”系列一炮而红的米哈游,IPO之路却也因为“崩坏”系列而折戟。近日,中国监证会网站披露的2020年度首次公开发行股票终止审查的企业名单中,上海米哈游网络科技股份有限公司赫然在列。根据官方信息,米哈游主动撤回上市申请材料,停止其在A股的IPO申请。至此,在2017年3月份首次提交IPO申请的米哈游,苦等了三年时间之后上市失败。从米哈游之前提交的招股书里可以看见,2012年成立的米哈游作为二次元游戏厂商,依靠着二次元的标签十分吃香。在2014年-2017年上半年,米哈游分别实现营收为1.03亿元、1.75亿元.4.42元、5.88亿元;净利润分别为0.66亿元、1.27亿元、2.73亿元、4.47

  • ​在tinycolinux上安装chrome

    本文关键字:chromeasdesktopshell,uniformwebosforadminanduser一个APP总是由UI,中间件,业务逻辑组件,但唯有UI足以划分一个appstack,因为UI是一个APP必须的部分,即使是console也有TUI,现今我们看到的UI主要有二种,随OS发布的原生GUI,和随着webapp发展出来的WEBPAGEGUI,但实际上若好好归纳一下,VNC也是一种远程控制专用GUI。硬件加速GL,DX也是一种UI,它是游戏APP的GUI,概言之,用图形或非图形技术实现的交互,只要它混合其它栈元素组成开发发布单元,它其实就可以是一种UI(你可以看到语言库和大型IDE中项目模板往往就是按appstack和UI类型组织的),只不过技术实现上,因为WEB的UI往往是一种HTML渲染引擎的东西,所以它其实属于基于原生UI的高级UI,但是,无论如何,一种OS使用某种高级UI并以此建立起全部的APP生态是可能的,如果有这样一种OS,那么就法上它可以称为该UI的OS。chromeos,webos就是这种东西,它展现的是webpage使用的appmodel完成的是weba

  • Q2studio学习笔记三

    1.Feature表统计继续我的qiime2图形界面q2studio学习笔记,之前已经获得了featuretable,现在对这个表做个统计。依旧是很简单的,选择featuretable--visualization-summarizetable,这里是需要实验设计文件(metadata)的,最好放上,这里我就不放了。点run之后,很快就有结果了。结果就像教程里的那样,2.代表序列统计这也没什么好说的,统计一下代表性的序列。使用featuretaable里的viewsequenceassociatedwitheachfeature选项,然后程序会自动载入数据,执行即可。结果如图:3.建树:用于多样性分析3.1多序列比对alignment--denovamultiplealignmentwithmafft,中间不小心报错,原因不明,但显示已完成,先放这。3.2移除高变区应该是这个alignment--Positionalconservationandgapfiltering.默认参数试试,因为命令行没有给出参数。3.3建树phylogeny--constructaphylogenetict

  • 01月29日【Python3 基础知识】

    01月29日【Python3基础知识】5.4参数匿名函数字典排序 5.5生成式和生成器 5.6装饰器的作用 5.4参数匿名函数字典排序#*元组;**字典 defadd(*args): total=0 foriinargs: total+=i print("total={0}".format(total)) defsortDictValue(dict1): print(sorted(dict1.items(),key=lambdad:d[1],reverse=False)) if__name__=='__main__': add(1,2,3,4,5) s1=lambdax,y:x+y #defs1(x,y): #returnx+y print(s1(10,20)) aaa=dict(a=100,b=10,c=50,d=321) l=list() sortDictValue(aaa)复制5.5生成式和生成器了解return和yield的区别a=[x*xforxinrange(1,30)ifx%2==0] print(type(a)) b=(x*xfo

  • zookeeper使用

    版权声明:本文为博主原创文章,遵循CC4.0BY-SA版权协议,转载请附上原文出处链接和本声明。本文链接:https://blog.csdn.net/qq_37933685/article/details/82732999个人博客:https://suveng.github.io/blog/​​​​​​​源码:https://gitee.com/suwenguang/testzookeeper集群角色:leader主follower从observer观察者:不参与写的选举,但是提供读概念:数据模型 zookeeper的数据模型和文件系统类似,每一个节点称为:znode.是zookeeper中的最小数据单元。每一个znode上都可以 保存数据和挂载子节点。从而构成一个层次化的属性结构 节点特性 持久化节点:节点创建后会一直存在zookeeper服务器上,直到主动删除 持久化有序节点:每个节点都会为它的一级子节点维护一个顺序 临时节点:临时节点的生命周期和客户端的会话保持一致。当客户端会话失效,该节点自动清理 临时有序节点:在临时节点上多勒一个顺序性特性 会话 watcherzookeep

  • DenseNet详解

    一、概述作为CVPR2017年的BestPaper,DenseNet脱离了加深网络层数(ResNet)和加宽网络结构(Inception)来提升网络性能的定式思维,从特征的角度考虑,通过特征重用和旁路(Bypass)设置,既大幅度减少了网络的参数量,又在一定程度上缓解了gradientvanishing问题的产生.结合信息流和特征复用的假设,DenseNet当之无愧成为2017年计算机视觉顶会的年度最佳论文.卷积神经网络在沉睡了近20年后,如今成为了深度学习方向最主要的网络结构之一.从一开始的只有五层结构的LeNet,到后来拥有19层结构的VGG,再到首次跨越100层网络的HighwayNetworks与ResNet,网络层数的加深成为CNN发展的主要方向之一.随着CNN网络层数的不断增加,gradientvanishing和modeldegradation问题出现在了人们面前,BatchNormalization的广泛使用在一定程度上缓解了gradientvanishing的问题,而ResNet和HighwayNetworks通过构造恒等映射设置旁路,进一步减少了gradientva

  • [Spring框架] Spring中的 ContextLoaderListener 实现原理.

    前言:这是关于Spring的第三篇文章,打算后续还会写入AOP和Spring事务管理相关的文章,这么好的两个周末都在看code了,确实是有所收获,现在就来记录一下. 在上一篇讲解SpringIOC的文章中,每次产生ApplicationContext工厂的方式是:  ApplicationContextapplicationContext=newClassPathXmlApplicationContext("applicationContext.xml");这样产生applicationContext就有一个弊端,每次访问加载bean的时候都会产生这个工厂,所以这里需要解决这个问题. 解决问题的方法很简单,在web启动的时候将applicationContext转到到servletContext中,因为在web应用中的所有servlet都共享一个servletContext对象.那么我们就可以利用ServletContextListener去监听servletContext事件,当web应用启动的是时候,我们就将applicationContext装载到servl

  • iptables练习

    一、COMMAND1、列出所有链的规则:iptables-L,显示某条链的规则就是iptables-LINPUT详细信息:iptables-vnL2、清楚所有链的规则:iptables-F3、设置默认规则策略:iptables-PINPUTDROP,iptables-POUTPUTDROP,iptables-PFORWARDDROP(拒绝所有数据包)在虚拟机上改成:iptables-PINPUTACCEPT,远程连接才可用。4、添加规则,在INPUT链上添加规则,协议是tcp,目标端口号是21:iptables-AINPUT-ptcp–dport215、插入规则,在INPUT链上插入规则,协议是tcp,目标端口号是23,规则号是1:iptables-IINPUT1-ptcp–dport236、替换规则,在INPUT链上替换规则号1的iptables规则,将目标端口号更改为24:iptables-RINPUT1-ptcp–dport247、删除规则,在INPUT链上删除规则号是1的iptables规则二、match:基本规则匹配器1、指定协议:iptables-AINPUT-ptcp-j

  • 搞笑图组:程序员的项目周期

    一,需求审评会议进行中。二.开发阶段进行中….三,代码复查阶段四,测试阶段….五,需求突然要改….六,项目上线

  • 用R语言做时间序列分析(附数据集和源码)

    时间序列(timeseries)是一系列有序的数据。通常是等时间间隔的采样数据。如果不是等间隔,则一般会标注每个数据点的时间刻度。下面以timeseries普遍使用的数据airlinepassenger为例。这是十一年的每月乘客数量,单位是千人次。如果想尝试其他的数据集,可以访问这里:https://datamarket.com/data/list/?q=provider:tsdl可以很明显的看出,airlinepassenger的数据是很有规律的。timeseriesdatamining主要包括decompose(分析数据的各个成分,例如趋势,周期性),prediction(预测未来的值),classification(对有序数据序列的feature提取与分类),clustering(相似数列聚类)等。这篇文章主要讨论prediction(forecast,预测)问题。即已知历史的数据,如何准确预测未来的数据。先从简单的方法说起。给定一个时间序列,要预测下一个的值是多少,最简单的思路是什么呢?(1)mean(平均值):未来值是历史值的平均。(2)exponentialsmoothin

  • php+mysql动态网站开发案例课堂_用php写一个网页页面

    大家好,又见面了,我是你们的朋友全栈君。在这篇文章中,我尽量用最浅显易懂的语言来说明使用PHP,MySQL制作一个动态网站的基本技术。阅读本文需要简单的HTML基础知识和(任一编程语言的)编程基础知识(例如变量、值、循环、语句块的概念等)。PHP基础概述PHP是一种解释性语言,可用于对网页进行预处理。PHP脚本在服务器端运行,其运行结果是一个可用来显示的网页。尽管可以完成许多类似工作,但是JavaScript和PHP的一大区别就是,JavaScript是在浏览器端运行的。事实上,浏览器会接收JavaScript代码并运行它,所以用户是可以查看JavaScript代码的。而PHP不会将原始代码交给浏览器,只会将其运行的结果交给浏览器,所以用PHP处理用户登陆、用户权限等问题是安全可靠的。PHP与HTML实际编写的时候,通常采用的方式是建立扩展名为php的文件(网页文件本质上是文本文件)。编写php代码和编写html代码并没有多少区别,而最方便的地方在于,在一个php文件中,两种代码是可以混编的。规则:php代码需要包含在<?php...?>标签中,就像这样:<?php

  • rsync用法教程(已验证)

    一、简介 rsync是一个常用的Linux应用程序,用于文件同步。 它可以在本地计算机与远程计算机之间,或者两个本地目录之间同步文件(但不支持两台远程计算机之间的同步)。它也可以当作文件复制工具,替代cp和mv命令。 它名称里面的r指的是remote,rsync其实就是"远程同步"(remotesync)的意思。与其他文件传输工具(如FTP或scp)不同,rsync的最大特点是会检查发送方和接收方已有的文件,仅传输有变动的部分(默认规则是文件大小或修改时间有变动)。 二、安装 如果本机或者远程计算机没有安装rsync,可以用下面的命令安装。 #Debian $sudoapt-getinstallrsync #RedHat $sudoyuminstallrsync #ArchLinux $sudopacman-Srsync 复制 注意,传输的双方都必须安装rsync。 三、基本用法 3.1-r参数 本机使用rsync命令时,可以作为cp和mv命令的替代方法,将源目录同步到目标目录。 $rsync-rsource/destination 复制 上面命令中,-r表示递归,即包含子

  • 20155308《信息安全系统设计基础 嵌入式C语言课堂考试补博客

    20155308《信息安全系统设计基础嵌入式C语言课堂考试补博客 知识点 置位 ?bits=bits|(1<<7); /*setsbit7*/ bits|=(1<<7); /*setsbit7*/ #defineSET_BIT(n,bits)do{bits|=(1<<n)}while(0) 清除 bits&=~(1<<7); /*clearsbit7*/ #defineCLR_BIT(n,bits)do{bits&=~(1<<n)}while(0) 反转位 bits^=(1<<6); /*flipsbit6*/ #defineFLIP_BIT(n,bits)do{bits^=(1<<n)}while(0) PPT上事例 提取位 插入位 理解代码 由于Seconds占5位,因此需要先右移5位将Minutes的最低位与位0对齐,再与上3F(0000000000111111)即可将6-15位全部清0,则获得minute部分。 0x3F出处为:对于m

  • Optimal Sum CodeForces - 182C

    原题链接 考察:思维 思路:   比较明显的是要用单调队列,在一段区间内,可以挑选一些数字变化符号.我们求的最大和只有两方式:尽量将负数变正数,尽量将正数变负数.   在枚举一段\(len\)区间,求最小的\(k\)个负数的绝对值和,然后剩下的数相加.每移动一位,和要做相应变化.所以需要记录左端点属于绝对值还是普通加减.这里利用\(muliset\)存储. Code #include<iostream> #include<cstring> #include<set> usingnamespacestd; typedeflonglongLL; constintN=100010; intn,len,nums[N],k; LLans=-1e14; voidsolve() { multiset<int>a,b; LLsum=0,res=-1e14; for(inti=1,j=1;i<=n;i++) { if(nums[i]>0) { b.insert(nums[i]); sum+=nums[i]; }e

  • CentOS7 通过systemd 添加开机重启服务

    现在越来越多的环境采用CentOS7作为基础配置,特别是Hadoop生态如果要测试或部署环境需要启动很多组件(zookeeper、kafka、redis等等),如下内容是在操作系统层实现开机启动,这样运维管理人员无需再每次硬件设备断电或计划内重启时去检查,从无聊的频繁工作中解脱出来。 Centos7的服务systemctl脚本一般存放在:/usr/lib/systemd,目录下又有user和system之分: /usr/lib/systemd/system  #系统服务,开机不需要用户登录就能运行的程序(相当于开机自启) /usr/lib/systemd/user    #用户服务,需要登录后才能运行的程序 第一步:在 /usr/lib/systemd/system目录下新建一个服务文件(例如zookeeper.service) cd /usr/lib/systemd/system touchzookeeper.service 使用vi工具编辑zookeeper.service文件,并添加以下内容: [Un

  • 微信打飞机

      最近微信一款打飞机游戏比较火,我也正在学习cocos2dx,所以利用cocos2dx和lua开发了这款打飞机游戏,只实现了部分功能,大家可以在这个基础上完善。游戏中的图片资源使用的是一款html5实现的打飞机的图片。 https://github.com/mercykevin/shipgame

  • apicloud 中常用的Api

    1.第一个函数:apiready.所有的js运行代码用到api的都要在这个函数内运行. 2.页面跳转:openWin,openFrame,Win与Frame的区别是Win的后退是返回到调用窗口或,而Frame是无法用后退.如果要刷新带参数reload:true就可以实现已经加载页面刷新 3.取控件的id:byId. 4.和服务器交互:mcm操作和post,get,文件的上传也是用post,只是api接口不同是file. 5.事件绑定:addEvt,用byId的控件绑定. 6.添加页面:通过文件菜单新建模板可以快速添加页面 7.真机调试:在模块中生成自定义loader,安装,然后在开发工具中查看ip和端口,在手机的应用的球中输入对应信息就可以调试了. 8.参数传递:在openWin,openFrame的时候传入参数,并在接收参数页用api.pageParam.xxx来获取参数 9.本地存储:用LocalStore来进行保存和获取.任何一个页面都可以执行这个操作

  • vue-quill-editor+vue-better-table结合使用,实现表格插入/合并等问题;

    首先项目集成以下两个依赖: vue-quill-editor:https://www.jianshu.com/p/8eb2bb78b641 vue-better-table:https://blog.csdn.net/sinat_27746197/article/details/105952089 最终文件结果: 下载 https://i.cnblogs.com/files 此链接中的src.zip文件 其中,src/commponents/quill/index.vue和src/view/editor/index.vue就是结合后的完美体现.   ,,,,,最后发现,插入表格的功能是有问题的,在src/view/editor/index.vue文件添加以下内容. handlers:{ table:function(){ //默认插入的表格行列数 this.quill.getModule("better-table").insertTable(); } }复制 insertColumnRight:{ text:'右边插入一列' }, insertCo

  • django学习第86天Django的Ajax文件上传.分页器.forms组件

    一.ajax上传 -ajax的文件上传 file对象=$("#myfile")[0].files[0] varformdata=newFormData() formdata.append(key,value) formdata.append(file,file对象) -$.ajax({ url:路径, type:'post', processData:false, contentType:false, data:formdata, //dataType:'json', success:function(data){ } } ) -编码格式:urlencode,form-data,json复制 模板cript: $("#filebtn").click(function(){ //js取到文件 varmyfile=$("#id_myfile")[0].files[0] //生成一个FormData对象 varformdata=newFormData() //放值 formdata.append('name',$("#id_name").val()) //formdata.appe

相关推荐

推荐阅读