【数据结构与算法】相交链表、环形链表(判断是否有环)、环形链表(返回入环节点)

news/2024/11/29 10:55:22/

主页:HABUO🍁主页:HABUO

🍁如果再也不能见到你,祝你早安,午安,晚安🍁


1.相交链表

题目:给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

示例:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

输出:Intersected at '8'

解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。 在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。 — 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。

分析:拿到这个题,我们最直接的想法就是能不能用我们之前的思想去解决,我们之前大多都是双指针解决的题,那这个题能不能解决呢?答案是肯定的,我们先观察下,如果下面的那个长的链表把多的那一个走了,之后长短链表一块走不久遇到了嘛,诶就是这样😃, 前面我们做了很多快指针要多走几步的题型,在这里我们又遇到了。因此大致思想就是:1.我们需要先知道谁长谁短。2.长的先走完长的步数。3.之后长短一块走,直至地址相同便是相交的节点

我们先计算两个链表的长度,具体如下:

//先求两个链表的长度,判断谁长谁短,长的长多少
Node* curA = headA;
Node* curB = headB;
int sizeA = 1;
int sizeB = 1;
while(curA)
{sizeA++;curA = curA->next;
}
while(curB)
{sizeB++;curB = curB->next;
}

之后就是判断谁长谁短,长的先走完长的步数,之后一起走。具体如下所示:

 //判断谁长if(sizeA > sizeB){int lenth_sub = sizeA - sizeB;//长的先走长的步数while(lenth_sub--){headA = headA->next;}//之后同时走while(headA != headB){if(headA == NULL)return NULL;headA = headA->next;headB = headB->next;}return headA;}//同样道理else{int lenth_sub = sizeB - sizeA;while(lenth_sub--){headB = headB->next;}while(headA != headB){if(headA == NULL)return NULL;headA = headA->next;headB = headB->next;}return headA;}

2.环形链表(判断是否有环)

题目:给你一个链表的头节点 head ,判断链表中是否有环。如果链表中存在环 ,则返回 true 。 否则,返回 false 。

示例1:

输入:head = [3,2,0,-4], pos = 1

输出:true

解释:链表中有一个环,其尾部连接到第二个节点。 

示例2:

 输入:head = [1], pos = -1

输出:false

解释:链表中没有环。 

分析:看到题我们还是同样的思想能不能用之前解题的方式解决,两个指针,一个快指针一个慢指针,要是有环,快指针是不是先进入环,当慢指针进环时,无论快指针走到哪,是不是就相当于在一个圆里面你追我赶了,只要快慢指针能相遇就说明链表里有环,如果快指针直接遍历完了整个链表后指向NULL,那就是没环。那这里就有了一个追上追不上的问题,虽然快指针走的快,它们之间的距离是逐渐缩小但是如果快靠近的时候跨过去了怎么办?因此必须这样的一个距离是一个单元一个单元缩小,不然无论是偶数还是奇数是不是都有可能永远遇不到,因为偶数如果每次缩小的距离都是奇数那么永远都遇不到, 奇数也是同样的道理。具体见下:

所以思想就是快指针走两步,慢指针走一步,只要遇到就是有环。实现如下:

bool hasCycle(struct ListNode *head) {struct ListNode *fast = head , *slow = head;while(fast && fast->next)//fast和fast->next不能为NULL,因为fast要走两步{fast = fast->next->next;slow = slow->next;if(slow == fast)//遇到就是有环return true;}return false; //走到这就是fast或者fast->next为NULL说明遍历了整个链表因此也就没环
}

3.环形链表(返回入环节点) 

题目:给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null不允许修改 链表

示例1:

输入:head = [3,2,0,-4], pos = 1

输出:返回索引为 1 的链表节点

解释:链表中有一个环,其尾部连接到第二个节点。

示例2:

输入:head = [1], pos = -1

输出:返回 null

解释:链表中没有环。

分析:这个题是上一个题的进阶版,上个题只需判断有没有环,这个题不但要有环而且还要返回环的入口节点,怎么做呢?前面有个相交链表,这能不能转换成相交链表呢?显然可以,为什么?因为我们判断环型链表时,是不是只要快慢指针相遇就是有环,那我们要是在这个相遇的这个节点断开是不是就是两个链表找相交节点,如下图所示:

但我说别这样做,前面我们可以看到光找相交节点工作量就比较大,何况我们还需要处理环呢,太繁琐,讨人烦,我们换一种方法,来点小学生的应用题,这不就是你追我赶的题嘛,来两个小方程不就解决了嘛,何必费那么大力气,我们假设slow走了L+X,那么fast是不是就走了2*(L+X),我们假设fast在人生道路上等待心上人等上了N圈,即N*C,是不是还有在slow身后走的X那段距离(众里寻他千百度,那人却在灯火阑珊处),那是不是就是2*(L+X)=L+X+N*C,好整理一下就是L=N*C-X诶发现了什么吗?(强调一遍,此时在fast与slow相遇处哦)是不是就是在相遇的这个点fast你随便走吧一定是走了N*C-X与头节点走了L相遇,那这次相遇就是环的入口节点(fast找到slow不容易啊,是不是回忆了一下这些年的心酸,走到当初那个岔路口思绪万千)。如下图所示:

在第二道环形题的基础上,我们只需让fast和head动起来即可,直至它们相遇,因为它们一定相遇💕。所以实现代码如下:

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast = head , *slow = head;while(fast && fast->next)//fast和fast->next不能为NULL,因为fast要走两步{fast = fast->next->next;slow = slow->next;if(slow == fast)//遇到就是有环{while(head != fast){head = head->next;fast = fast->next;}return fast;}}return NULL; //走到这就是fast或者fast->next为NULL说明遍历了整个链表因此也就没环
}

总结:本篇博客介绍了三道题,这三道题不约而同的有相似的部分,无论是相交链表,亦或是环形链表,这样新的结构,可以扩展我们的知识面,相信再以后面对不一样的题型时,我们仍然可以迎刃有余,希望大家都有所收获,相信本篇博客的学习我们受益匪浅!💯 


🌻数据结构算法专栏🌻

🏋不是每一粒种子都能开花,但播下种子就比荒芜的旷野强百倍🏋


http://www.ppmy.cn/news/1550879.html

相关文章

WPS文字学习计划与策略

一、学习目标 熟练掌握WPS文字的基本操作:包括新建、打开、保存文档,文本输入与编辑,段落设置,页面布局调整等。高效利用WPS文字的编辑功能:掌握样式设置、插入图表、批注功能等,提高文档编写的效率和质量。学会利用模板快速生成文档:能够根据需要选择合适的模板,快速生…

水母形状电池:助力机器人性能提升

大家好!今天来了解大容量水母机器人的水性电池——《The multifunctional use of an aqueous battery for a high capacity jellyfish robot》发表于《SCIENCE ADVANCES》。想象一下,在神秘的水下世界,水母机器人轻盈地游动,而这背…

Zemax孔径类型

系统孔径是描述光轴上通过光学系统的光束大小的重要参数,它对于光学系统的设计和性能分析至关重要。根据您提供的信息,我们可以详细解析系统孔径的类型和相关的类型代码,以及它们各自的定义和应用。 系统孔径类型和代码 入瞳直径&#xff0…

微服务怎样才能真正“微“起来

微服务这些年比较时髦,用 Java 取代 SQL 及存储过程开发业务逻辑,确实能获得架构上的优势,细节这里就不展开了,微服务能流行当然有它的道理。 但微服务真地“微”吗? 我们知道,面对同样业务逻辑时&#xf…

vscode可以编译通过c++项目,但头文件有红色波浪线的问题

1、打开 VSCode 的设置,可以通过快捷键 Ctrl Shift P 打开命令面板,然后搜索并选择 “C/C: Edit Configurations (JSON)” 命令,这将在 .vscode 文件夹中创建或修改 c_cpp_properties.json 文件 {"configurations": [{"name…

Java图书管理系统(简易保姆级)

前面学习了这么多知识,为了巩固之前的知识,我们就要写一个图书管理系统来帮助大家复习,让大家的知识融会贯通~~~ 话不多说,直接开始今天的内容~ 首先呢,我们要有一个大体的思路: 实现效果思路有两种情况&a…

Java核心技术教程:深入理解URL类的实例化与应用

大家好,这里是Java码牛! Java核心技术教程:深入理解URL类的实例化与应用 引言 在Java编程中,网络编程是一个重要的领域,而URL(统一资源定位符)类则是网络编程中的基础。本文将详细讲解Java中…

vscode远程连接ssh

一. 使用vscode里的ssh查件连不上远程的解决方法 删除Windows上的known_host文件,该文件会在连接之后自动生成,用于验证远程服务器的身份。 konwn_host和id_rsa,id_rsa.pub的关系 (1)konwn_host用于客户端验证远程服务…