【LeetCode链表#9】图解:两两交换链表节点

两两交换链表中的节点

力扣题目链接(opens new window)

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

24.两两交换链表中的节点-题意

思路

这里还是要应用虚拟头节点,不然交换链表头节点的操作会与交换其他节点时不同

交换的过程其实不难理解,但是代码实现过程需要注意很多细节

下面是交换过程的图解

首先,定义一个虚拟头节点

并让当前指针cur指向dummy head【注意:cur一定要在需要操作的两个节点之前】

然后按途中顺序将对应节点的next指好即可

注意:虽然画图我们很好理解,但是在操作过程中有很多细分步骤,如果直接上手写代码会很困惑

例如,当dummy指向节点2(也就是cur.next.next)后,dummy与原来的节点1就断开连接了

此时再想通过cur去寻找到节点1(cur.next)就行不通了,进而节点2也就无法指向节点1,步骤②无法继续进行

与翻转链表时类似,我们需要一个临时节点temp先去保存节点1

让节点2通过指向temp的方式找到节点1

ps:为什么不存节点2?因为步骤①之后节点2就已经是cur.next了,而dummy是不会变的,所以怎么都能找到节点2

当节点2指向temp(储存有cur.next)后,节点2与原来的节点3就断开连接了

同理,我们应该把节点3也用临时节点保存,这里用temp1保存

于是节点2指向节点3的过程就变成了:

temp1是节点3的备份,它后面还是和节点4连着,所以不用担心找不到节点4

至此,节点1与节点2完成了交换,cur移动到cur.next.next(即交换后此处为节点1,是什么节点并不重要,反正待会交换的又不是当前cur指向的节点,而是后两个节点),展开后的结果如下:

链表节点数为奇数时,结束条件:cur.next.next = null

链表节点数为偶数时,结束条件:cur.next = null

代码

思路通过画图可以很好理解,但是代码实现又有很多坑

class Solution {
    public ListNode swapPairs(ListNode head) {
        //定义虚拟头节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;//虚拟头节点指向head
        ListNode cur = dummy;

        //定义临时节点用于保存节点1、3
        ListNode temp;
        ListNode temp1;
        

        //遍历链表
        //注意这里的结束条件,链表节点数为奇偶情况下是不同的
        //需要先验证cur.next再验证cur.next.next
        //要不然如果是偶数个节点你先验cur.next.next直接就空指针异常了
        while(cur.next != null && cur.next.next != null ){
            //这里下意识肯定就想开始交换了,但如果不先保存节点就会出现空指针异常
            temp = cur.next;
            temp1 = cur.next.next.next;
            cur.next = cur.next.next;//dummy换2
            cur.next.next = temp;//2换1
            cur.next.next.next = temp1;//1换3
            cur = cur.next.next;//移动cur至新的待交换的两个节点前

        }
        //遍历结束,返回dummy的下一个节点即可
        return dummy.next;
    }
}

易错点:
1、创建完dummy后记得指向head

2、交换过程中要以cur为参照点来表示参与交换的节点,不要变,例如1换3时不能写成

`temp.next = temp1;

本文转载于网络 如有侵权请联系删除

相关文章

  • Go语言GC实现原理及源码分析

    转载请声明出处哦~,本篇文章发布于luozhiyun的博客:https://www.luozhiyun.com/archives/475本文使用的Go的源码1.15.7介绍三色标记法三色标记法将对象的颜色分为了黑、灰、白,三种颜色。黑色:该对象已经被标记过了,且该对象下的属性也全部都被标记过了(程序所需要的对象);灰色:该对象已经被标记过了,但该对象下的属性没有全被标记完(GC需要从此对象中去寻找垃圾);白色:该对象没有被标记过(对象垃圾);在垃圾收集器开始工作时,从GCRoots开始进行遍历访问,访问步骤可以分为下面几步:GCRoots根对象会被标记成灰色;然后从灰色集合中获取对象,将其标记为黑色,将该对象引用到的对象标记为灰色;重复步骤2,直到没有灰色集合可以标记为止;结束后,剩下的没有被标记的白色对象即为GCRoots不可达,可以进行回收。流程大概如下:TRI-COLOR下面我们来说说三色标记法会存在的问题。三色标记法所存在问题多标-浮动垃圾问题假设E已经被标记过了(变成灰色了),此时D和E断开了引用,按理来说对象E/F/G应该被回收的,但是因为E已经变为灰色了,其仍会被当作存活

  • 热门问题Q&A

    点击蓝字 关注我们无论你是正在使用腾讯云CDN的用户还是对腾讯云CDN技术感兴趣,相信都有或多或少的问题,这里希蒂恩将会为大家解答一些常见的问题,希望能够对你有帮助哦~Q1接入CDN后,源站需要改造才能享受加速服务吗?基本不需要。但是为了能够达到更好的加速效果,我们建议您先做动静分离,动态文件和静态文件分配在不同域名下,仅需要对静态资源做加速。Q2如何获取客户端真实IP?请求通过边缘加速节点后,会增加x-forward-for头部,携带客户端真实IP信息。Q3CDN子用户如何配置?子用户本身无需注册腾讯云、开通CDN服务,子用户由创建者将其添加至子用户列表中。Q4域名接入CDN之后,如何绑定CNAME?您可以参考CNAME配置文档中的操作说明,在您的DNS服务商处绑定CNAME。Q5CDN是否支持泛域名接入?CDN目前已经支持泛域名接入,但需要进行域名归属权验证,验证通过后方可接入或取回域名。Q6关闭加速服务后,域名配置会保留吗?关闭后的域名配置会保留,但不会继续为您提供加速服务,此时用户请求会返回404状态码。Q7CDN支持的业务类型有哪些?务类型选择,决定了域名调度的资源平台,不同

  • Python爬虫入门教程 56-100 python爬虫高级技术之验证码篇2-开放平台OCR技术

    今日的验证码之旅今天你要学习的验证码采用通过第三方AI平台开放的OCR接口实现,OCR文字识别技术目前已经比较成熟了,而且第三方比较多,今天采用的是百度的。注册百度AI平台官方网址:http://ai.baidu.com/ 接下来申请 接下来创建一个简单应用之后,就可以使用了,我们找到 阅读文字识别相关文档你需要具备基本的阅读第三方文档的能力,打开我们需要的文档https://cloud.baidu.com/doc/OCR/OCR-API.html#.E9.80.9A.E7.94.A8.E6.96.87.E5.AD.97.E8.AF.86.E5.88.AB这个页面基本上已经把我们需要做的所有内容都已经标识清楚了编写获取accesstoken的代码在目前主流的API开发模式下,都是需要你进行accesstoken的获取的代码如下,重点需要参照文档进行传参的设计 defget_accesstoken(self): res=requests.post(self.url.format(self.key,self.secret),headers=self.header) content=res

  • 一日一技:在Python中使用类型标注

    由于Python是动态语言,不需要为变量提前设定类型,这为开发提供便捷的同时也带来了一些麻烦。有这样一段代码:classRobot(object): def__init__(self): self.name='Cruse' defwalk(self): print('Iamwalk.')复制我定义了一个类Robot,这个类有一个属性name和一个方法walk。接下来我又定义了一个函数run_a_robot,这个函数接收一个参数robot_object,这个参数是Robot类的一个实例。在函数里面,我希望使用这个实例的属性和方法。但此时,可以看出,PyCharm的自动补全功能失效了。它不知道robot_object这个变量是什么东西,没有办法帮我补全这个实例的属性和方法名。如下图所示。个时候,如果你使用的是Python3,那么你可以使用类型标注来告诉PyCharm,这个robot_object是Robot类的一个实例,从而使PyCharm提供自动补全。如下图所示。型标注的格式为变量名:类型=值复制举一个例子:age:int=24#定义一个变量a

  • 【Python Tip】Anaconda套件下如何把scikit-learn包更新到0.20版本?

    笔者邀请您,先思考:1如何进行Python包更新?问题背景因为使用sklearn.compose下的函数make_column_transformer,发现它是在scikit-learn包的0.20版本里面,如何在Anaconda套件下进行更新呢?解决方案首先想到使用condaupdate的命令进行更新,结果显示当前的Anacond还没有更新到0.20版本,故更新失败。 接下来,利用condaremove删除scikit-learn包,命令如下:1condaremovescikit-learn复制下载0.20的scikit-learn包,链接如下: https://www.lfd.uci.edu/~gohlke/pythonlibs/#scikit-learn说明:因为Anaconda套件使用Python3.6使用pipinstall进行本地化安装,命令如下:1pipinstallE:\PythonLibs\scikit_learn-0.20-cp36-cp36m-win_amd64.whl复制测试scikit-learn是否更新成功,代码片段如下:1importsklearn 2pr

  • Mac安装Jenkins系列

    简介Jenkins是一个开源软件项目,是基于Java开发的一种持续集成工具,用于监控持续重复的工作,旨在提供一个开放易用的软件平台,使软件的持续集成变成可能。优点:持续的软件版本发布/测试项目。监控外部调用执行的工作。使用Jenkins持续化集成,可以帮助开发人员,缩减开发周期,快速迭代版本,开发人员只关注开发任务,像给测试、产品、市场人员打包等等,这些任务就可以交给其他人员来完成,利用Jenkins的优点,只需要点击构建项目,就能完成自动打包,测试人员也只需要扫一下二维码即可安装,很方便,这也算是给测试带来的便利。安装登录Jenkins官网下载Jenkins;image.png点击Download:image.pngimage.png备注:需要注意的是在下载的时候勾选Mac平台下的pkg包。下载下来以后,双击即可安装,安装时第一步是输入密码:image.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.png安装完成之后,Safari可能会自动打开,如果没有自动打开,打开浏览器,输入http://localhost:8080在

  • 云计算的信心危机?不要惊慌:这很正常

    最终,专家预计在2022年,一些数字温和派可能会说服他们的首席执行官、首席财务官和首席信息安全官采用。实际上,更好的业务分析和混合云环境可以并且将为他们提供原先预期的结果。你还记得第一次听到“云计算”这个术语是什么时候吗?显然,如果人们忽略了20世纪60年代诞生的数据中心模型。1994年的一篇名为“Bill&Andy的优秀冒险II”的文章中首次提到了“云计算”,这是一篇主要描述Telescript的分布式编程语言的文章。康柏公司首次提到云计算这个术语出现在该公司1996年的内部文件中。而在2006年,谷歌公司当时的首席执行官EricSchmidt在一次行业会议上使用了这个术语,而在同一年,亚马逊公司创建了子公司亚马逊网络服务公司(AWS)时,并推出了其弹性计算云(EC2)。对大多数人来说,可能是在那时听说了“云计算”这个术语。如果是2006年首次听说的话,那么已经是12年前了。虽然网络服务商、应用程序服务提供商、存储服务提供商以及SaaS提供商都已经走了很长的发展之路,但似乎只有在过去的三四年中,大多数企业才开始急于采用云计算。风起云涌这种匆忙的应用已不再是前8年普遍存在的相对

  • 麦肯锡160页报告:2030年全球将可能有8亿人要被机器抢饭碗

    安妮编译自麦肯锡官网 量子位出品|公众号QbitAI自动化方便了生活,也改变了工作。但自动化对人类工作有何影响,未来的就业机会够不够,我们怎样适应即将到来的职业转换呢?近日,麦肯锡发布了一篇题为《Jobslost,jobsgained:Workforcetransitionsinatimeofautomation》的研究报告,完整报告以160页的篇幅具体阐明了自动化带来的影响。量子位挑其报告重点整理如下,与大家分享——4亿-8亿人将失业麦肯锡预计,到2030年,全球将有4亿到8亿人将被自动化取代,相当于今天全球劳动力的五分之一。自动化对工作的影响为何如此大?据统计,在全球60%的职业中,至少三分之一组成活动可以被自动化代替。也就是说,职业转化对人类社会的影响意义重大。自动化对就业的潜在影响因职业和部门而异——最容易受到自动化影响的活动包括可预测环境中的物理活动(如操作机械和准备快餐)、收集和数据处理活动,这些工作可以通过机器做得更好更快。这可能会取代大量的劳动力,例如抵押贷款发放、律师助理工作、会计和后勤事务处理等。是否有充足的就业机会?历史数据表明,科技能够创造就业。△美国1850-

  • Ansible-command模块和shell模块

    ansiblecommand与shell模块两个模块都是用于执行linux命令的,这对于命令熟悉的工程师来说,用起来非常high。shell模块与command模块差不多(command模块不能执行一些类似$HOME,>,<,|等符号,但shell可以)https://docs.ansible.com/ansible/latest/modules/command_module.htmlhttps://docs.ansible.com/ansible/latest/modules/shell_module.html一、shell模块[root@manage01~]#ansible-mshell192.168.98.201-a"ls/root" 192.168.98.201|CHANGED|rc=0>> 公共 模板 视频 图片 文档 下载 音乐 桌面 anaconda-ks.cfg initial-setup-ks.cfg nginx.service nginx_study [root@manage01~]#ansible-mshell192

  • IEEE Fellow 李学龙:多模态认知计算是实现通用人工智能的关键

    信容=信息量/数据量作者|李梅编辑|陈彩娴在如今数据驱动的人工智能研究中,单一模态数据所提供的信息已经不能满足提升机器认知能力的需求。与人类利用视觉、听觉、嗅觉、触觉等多种感官信息来感知世界类似,机器也需要模拟人类联觉来提升认知水平。同时,随着多模态时空数据的爆发和计算能力的提升,研究者已经提出了大量方法以应对日益增长的多样化需求。但当前的多模态认知计算仍局限于人类表观能力的模仿,缺乏认知层面的理论依据。面对更加复杂的智能任务,认知科学与计算科学的交叉已成必然。近日,西北工业大学的李学龙教授在《中国科学:信息科学》期刊上发表了《多模态认知计算》一文,以“信容”(InformationCapacity)为依据,建立了认知过程的信息传递模型,提出了“多模态认知计算能够提高机器的信息提取能力”这一观点,从理论上对多模态认知计算各项任务进行了统一。李学龙认为,多模态认知计算是实现通用人工智能的关键之一,在”临地安防”(VicinagearthSecurity)等领域有广阔的应用前景。本文探索了人类和机器的统一认知模式,对推动多模态认知计算的研究带来启发。引用格式:XuelongLi,“Mult

  • 【Java】ArrayList源码

    Thetimeyouspendonyourrosesmakesyourrosessoimportant.ArrayList源码分析packageNote.cistern; importjava.util.ArrayList; publicclassArrayListDemo{ publicstaticvoidmain(String[]args){ ArrayList<Object>arrayList=newArrayList<>(); arrayList.add("e"); } }复制属性和构造方法:privatestaticfinallongserialVersionUID=8683452581122892189L; /** *默认的初始容量 */ privatestaticfinalintDEFAULT_CAPACITY=10; /** *初始化一个空实例时的数组 */ privatestaticfinalObject[]EMPTY_ELEMENTDATA={}; /** *缺省空对象数组 */ privatestaticfin

  • leetcode-29. 两数相除

    JAVA解法classSolution{ publicintdivide(intdividend,intdivisor){ //被除数为0直接返回结果 if(dividend==0){ return0; } //防止溢出 if(dividend==Integer.MIN_VALUE&&divisor==-1){ returnInteger.MAX_VALUE; } //设置一个判断是否异号的标志位,true则为异号 booleanflag; //利用异或来判断两个数是否异号 flag=(dividend^divisor)<0; //将两个数强转为long型并取绝对值 longd=Math.abs((long)dividend); longr=Math.abs((long)divisor); //定义存储最终结果的变量 intresult=0; /** 这里是逆向思维:先把被除数左移i位,i的值从31开始递减, 当被除数/2^i的值刚好出现大于等于除数的时候,说明这时 候要求的商已经出现,并且大于除数的部分就是余数。这时候, 2^i就是商,但是此时循环要怎么退出来呢

  • R绘图练习 | 突出显示个别条形的重叠条形图

    ?专注R语言在?生物医学中的使用首先是加载R包和数据library(tidyverse) library(ggtext) library(showtext) showtext_auto() load("E:/R/r-learning/r4ds/000files/df_animals_2.rdata") 复制主题设置theme_set(theme_minimal(base_size=19,base_family="Girassol")) theme_update( text=element_text(color="grey12"), axis.title=element_blank(), axis.text.x=element_text(family="IosevkaCurly"), axis.text.y=element_blank(), panel.grid.major.y=element_blank(), panel.grid.minor=element_blank(), plot.margin=m

  • 【Tensorflow】结果可复现设置-随机种子设置(Random Seed)

    目录引言设置 引言 在进行深度学习实验的时候,可能经常会发现,虽然输入的数据都是一样的,但是输出的结果总是会有不同的波动,这主要是由于在神经网络中,很多网络层参数的初始化会涉及到随机,这个就会导致最终的结果会有一些差距,因此如果我们想要固定某一个结果,并复现这个结果,我们就需要提前设置固定的随机种子 设置 一般来说,我们可以通过对每一层的网络层设置固定的随机种子,保持结果可复现,但是显然这是比较麻烦的一件事,所以我们可以通过tf.random.set_seed()来全局固定CPU上的随机性,但是当我们使用GPU训练时,则无法起作用,需要通过tensorflow-determinism库来实现在GPU上固定随机性 #pipinstalltensorflow-determinism #tensorflow-determinism=0.3.0 #tensorflow=2.9.1 importrandom importnumpyasnp importtensorflowastf random_seed=42 random.seed(random_seed)#setrandomseedfo

  • RDIFramework.NET敏捷开发框架WinForm新增文件中心-实现附件集中管理

    1、引言 文件中心类似附件管理是一个非常实用功能,可以归档自己平时所需要的文件,也可以把文件分享给别人,更像一个知识中心。文件中心主界面如下图所示,左侧“附件分类”展示了用户对文件的分类,只能自己看到,“共享文件”中的文件所有用户都可以看到。选择一个分类,右侧列出了当前分类的所有文件,对于上传的文件没有格式要求,对于已上传的文件也可以下载下来。同时可对常用格式的文件(pdf、word、excel、PPT、图片文件、文本文件等)进行在线预览、打印等。 左侧选择对应文件分类后,右侧会展示对应的文件,根据需要我们可以上传文件,删除、下载文件、在线预览上传的文件等。注意左侧的附件分类有一个特殊的分类叫“表数据文件”,这个是我们通过我们的一个“通用附件”控件针对特定表进行上传的文件。这儿只展示了我们自己上传的文件,非常的实用。 表数据文件:此类型的文件不能在这儿上传(只能通过业务表单上传),但在这儿可以下载,预览,超级管理员可以删除。 个人文件:此类型只加载自己上传的文件,私有空间,别人上传的文件不能看到,同时自己上传的文件可以自己随便管理(增、删等) 共享文件:此类型的文件只要上传了其他用户

  • web安全

    utf-7 XSS:http://lcx.cc/?i=2862

  • java并发编程(五)正确使用volatile

    转载请注明出处:   volatile用处说明   在JDK1.2之前,Java的内存模型实现总是从主存(即共享内存)读取变量,是不需要进行特别的注意的。而随着JVM的成熟和优化,现在在多线程环境下volatile关键字的使用变得非常重要。   在当前的Java内存模型下,线程可以把变量保存在本地内存(比如机器的寄存器)中,而不是直接在主存中进行读写。这就可能造成一个线程在主存中修改了一个变量的值,而另外一个线程还继续使用它在寄存器中的变量值的拷贝,造成数据的不一致。 要解决这个问题,就需要把变量声明为volatile(也可以使用同步,参见http://blog.csdn.net/ns_code/article/details/17288243),这就指示JVM,这个变量是不稳定的,每次使用它都到主存中进行读取。一般说来,多任务环境下,各任务间共享的变量都应该加volatile修饰符。 Volatile修饰的成员变量在每次被线程访问时,都强迫从共享内存中重读该成员变量的值。而且,当成员变量发生变化时,强迫线程将变化值回写到共享内存。这

  • keras load_model ValueError: Unknown initializer: GlorotUniform

    在服务器上使用keras对数据进行训练完成后,通过save的方法将模型保存成对应的xxxxx.h5文件,将对应的h5文件拷贝到windows下面的时候通过load命令加载却报错。 报错如下: kerasload_modelValueError:Unknowninitializer:GlorotUniform。 这是因为在服务器上安装keras时候是在tensorflow里面进行的,而Windows下面进行加载的时候导入的却是keras下面的加载模型,把对应的导入模块进行替换即可。 fromkeras.modelsimportload_model #将上面的这句话替换成下面的,即可。 fromtensorflow.keras.modelsimportload_model #在执行此句就不会报错了 model=load_model('lstm_model.h5')复制  

  • 依赖包排查过程

    错误信息 Causedby:org.apache.catalina.LifecycleException:Achildcontainerfailedduringstartatorg.apache.catalina.core.ContainerBase.startInternal(ContainerBase.java:953)atorg.apache.catalina.core.StandardEngine.startInternal(StandardEngine.java:262)atorg.apache.catalina.util.LifecycleBase.start(LifecycleBase.java:150)...27moreCausedby:java.util.concurrent.ExecutionException:org.apache.catalina.LifecycleException:Failedtostartcomponent[StandardEngine[Tomcat].StandardHost[localhost]]atjava.util.concurre

  • [loj6746]区间众数

    枚举区间中点$x$,考虑$L$使得$x$为区间$[x-L,x+L]$的众数: 记可重集$\{|i-x|\mida_{i}=x\}$中的元素依次为$b_{1}\leb_{2}\le...\leb_{k}$ 枚举出现次数$i\in[1,k]$,即要求$L\in[b_{i},b_{i+1})$,且合法的$L$是该区间的一个前缀 当$k\ge\sqrt{n}$时,这类$x$仅有$o(\sqrt{n})$个,直接从小到大枚举$L$并维护众数即可 当$k<\sqrt{n}$时,预处理出$pos_{r,i}$表示以$r$为右端点且众数出现次数$>i$的左端点 此时,条件即$pos_{x+L,i}<x-L$,移项后$L+pos_{x+L,i}$具有单调性,二分即可 具体实现中,$pos$可以用双指针求出,且需交换$i$和$x$的枚举顺序(空间限制) 上述过程复杂度为$o(n\sqrt{n})$(注意二分仅有$n$次),并转换为以下问题: 给定$n$组$(x,l_{L},r_{L})$,$m$次询问$\sum_{(x,l_{L},r_{L})}[l_{L},r_{L}]\cap[0,

  • 实现MFC扩展DLL中导出类和对话框

    如果要编写模块化的软件,就要对对动态链接库(DLL)有一定的了解,本人这段时间在修改以前的软件时,决定把重复用的类和对话框做到DLL中,下面就从一个简单的例子讲起,如何实现MFC扩展DLL中导出类和对话框。    一、创建MFC扩展DLL  步骤:   运行VisualStudio6.0->File->New...->Projects;   选择MfcAppWizard(dll),在右边Projectname下输入ExportClass,单击“下一步”;   选择MfcExtensionDLL(usingshareMFCDLL)单击“finish”;   以上完成建立扩展DLL的框架,下面接着建立输出类:  Insert-> NewClass...在打开的对话框中,"ClassType"选择"GenericClass",ClassName中输入CDogClass(当然你可以用其它的名称,我喜欢小狗,所有用它了,在"BaseClass"下输入CObject,然后"OK";为类添

相关推荐

推荐阅读