代码随想录算法训练营Day4 | 24.两两交换链表中的节点、19删除链表中的第N个节点、链表相交、142.环形链表

本文主要是介绍代码随想录算法训练营Day4 | 24.两两交换链表中的节点、19删除链表中的第N个节点、链表相交、142.环形链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

24.两两交换链表中的节点

题目:给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

题目链接:24. 两两交换链表中的节点

卡哥的视频讲解:帮你把链表细节学清楚! | LeetCode:24. 两两交换链表中的节点

题目思考:定义一个虚拟头节点,对该节点后的两个节点进行操作,注意判断可循环条件以及定义变量来暂时储存节点。

交换过程如图:

代码示例:

代码逻辑详解:

  1. 首先创建一个虚拟头节点 dumyhead,值为 -1,并将其指向链表的头节点 head。这样做是为了处理头节点的特殊情况。

  2. 创建指针 cur 指向虚拟头节点 dumyhead,用于遍历链表。

  3. 创建临时指针 temp 用于指向待交换节点的前一个节点,即第一个要交换的节点的前一个节点。

  4. 创建临时指针 temp1 用于指向待交换节点的后一个节点的后一个节点,即第二个要交换的节点的后一个节点。

  5. 创建两个指针 firstsecond 分别指向待交换的两个节点。

  6. 进入循环,条件是 cur.nextcur.next.next 都不为 null,即链表中至少有两个节点。这样做是为了保证交换的两个节点是相邻的。

  7. 在循环中,首先保存好要交换的两个节点及其前后节点的位置,以便后续指针操作。

  8. cur.next 指向第二个节点 second,即将第二个节点提前。

  9. second.next 指向第一个节点 first,完成交换。

  10. first.next 指向之前保存的 temp1,即将第一个节点的下一个节点指向原来第二个节点的后一个节点。

  11. cur 指向交换后的第一个节点,为下一轮交换做准备。

  12. 循环结束后,返回虚拟头节点的下一个节点,即交换后的链表的头节点。

这样,整个链表中相邻节点的交换就完成了。

leetcode提交记录:

小tips:

1.先把节点交给指针之后,再进行交换,别忘了设置两个temp值

2.注意循环的条件,这里巧妙地将链表个数为偶数和奇数的情况都囊括了,当链表个数为偶数时,如果cur的下一个为空,则停止循环,如果链表个数为奇数时,则还需要同时满足cur下一个的下一个为空才会停止循环,这也是为什么只能用和而不能用或。注意!!

                     cur.next != null&&cur.next.next != null
这两个条件的顺序不能调换,否则会报空指针异常的错误。

19.删除链表的倒数第N个节点

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

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

卡哥的视频链接:链表遍历学清楚! | LeetCode:19.删除链表倒数第N个节点

题目思考:要找到删除的节点,就要知道它的上一个节点是什么,我开始的想法是把链表反转过来,直接删除第n个节点,但是这个操作就复杂了,可以直接使用快慢指针。假如要删除倒数第n个节点,则让快指针先走n+1步(+1是为了让慢指针指向被删除节点的前一个),再让快慢指针同时走,当快指针指向空时,慢指针就走到被删除节点的前一个了。(如下图)

代码示例:

代码详细逻辑:

  1. 首先创建一个虚拟头节点 dummyhead,值为 -1,并将其指向链表的头节点 head。这样做是为了处理删除头节点的特殊情况。

  2. 创建两个指针 fastslow,都指向虚拟头节点 dummyheadfast 指针先向前移动 n+1 步,使其与 slow 指针相隔 n 个节点。

  3. 进入循环,条件是 fast 指针不为 null。在循环中,fast 指针和 slow 指针同时向前移动,直到 fast 指针指向 null,即到达链表的末尾。

  4. 循环结束后,slow 指针指向要删除节点的前一个节点,而 fast 指针指向要删除节点的后一个节点。

  5. 将要删除节点的前一个节点 slownext 指针指向要删除节点的下一个节点,从而将要删除的节点从链表中删除。

  6. 返回虚拟头节点的下一个节点,即删除节点后的链表的头节点。

这样,就完成了删除链表中倒数第 n 个节点的操作。

leetcode提交记录:

小tips:

1.一定要记得是让快指针走n+1步,这样慢指针才可以指向被删除节点的前一位,方便操作

2.定义快慢指针时,一定要定义在虚拟头节点的位置,如果在 head 的位置初始化快慢指针,那么在处理删除头节点的情况时就会变得复杂。因为如果要删除的是头节点,需要同时更新头节点 head 的位置,而且要处理头节点的特殊情况可能会引入更多的边界条件。

通过使用虚拟头节点 dummyhead,可以避免对头节点的特殊处理。虚拟头节点实际上是一个哨兵节点,它位于链表的头部,但不存储任何有效数据。这样,在处理链表的逻辑中,就可以统一对待头节点和其他节点,简化了代码逻辑,提高了代码的可读性和可维护性。

这篇关于代码随想录算法训练营Day4 | 24.两两交换链表中的节点、19删除链表中的第N个节点、链表相交、142.环形链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/920309

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

macOS无效Launchpad图标轻松删除的4 种实用方法

《macOS无效Launchpad图标轻松删除的4种实用方法》mac中不在appstore上下载的应用经常在删除后它的图标还残留在launchpad中,并且长按图标也不会出现删除符号,下面解决这个问... 在 MACOS 上,Launchpad(也就是「启动台」)是一个便捷的 App 启动工具。但有时候,应

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤