代码随想录算法训练营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

相关文章

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

redis过期key的删除策略介绍

《redis过期key的删除策略介绍》:本文主要介绍redis过期key的删除策略,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录第一种策略:被动删除第二种策略:定期删除第三种策略:强制删除关于big key的清理UNLINK命令FLUSHALL/FLUSHDB命

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到