【刷题专栏—突破思维】142. 环形链表 II

在这里插入图片描述

前言:本篇博客将讲解三个OJ题,前两个作为铺垫,最后完成环形链表的节点的寻找

文章目录

  • 一、160. 相交链表
  • 二、141. 环形链表
  • 三、142. 环形链表II

一、160. 相交链表

题目链接:LeetCode—相交链表

题目描述:
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
图示两个链表在节点 c1 开始相交:
在这里插入图片描述
注意,函数返回结果后,链表必须 保持其原始结构 。
评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。

示例1:
在这里插入图片描述
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at ‘8’
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。

示例2:
在这里插入图片描述
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。
由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
这两个链表不相交,因此返回 null 。


题目解析:

  1. 遍历链表计算长度: 初始化两个指针curA和curB分别指向链表headA和headB的头节点,然后遍历链表,分别计算链表的长度lenA和lenB,来到尾节点时比较是否一致,一致说明链表相交;否则,不相交,即可返回NULL。
  2. 对齐起点:如果尾节点相同,计算两个链表长度的差值n,然后选取较长链表的头节点为longList,较短链表的头节点为shortList。然后,将longList指针向后移动n个位置,使得两个链表剩余长度相等。
  3. 寻找交点: 同时遍历longList和shortList,找到它们第一个相同的节点,即为交点。

代码实现:

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    ListNode* curA = headA, *curB = headB;
    // 初始化链表headA和headB的长度分别为1,原因是curA和curB初始化就指向头
    int lenA = 1, lenB = 1;

    // 计算链表headA的长度
    while (curA->next) {
        lenA++;
        curA = curA->next;
    }

    // 计算链表headB的长度
    while (curB->next) {
        lenB++;
        curB = curB->next;
    }

    // 如果链表headA和headB的尾节点不相同,说明它们没有交点,返回NULL
    if (curA != curB) {
        return NULL;
    }

    //abs 函数是 C 语言标准库(<stdlib.h> 头文件)中的一个函数,用于返回整数的绝对值
    int n = abs(lenA - lenB);
    // 初始化指针longList和shortList,分别指向较长和较短的链表头部
    ListNode* longList = headA, *shortList = headB;

    // 如果链表headA较短,调整longList和shortList的指向
    if (lenA < lenB) {
        longList = headB;
        shortList = headA;
    }

    // 将较长链表指针向后移动,使两个链表剩余长度相等
    while (n--) {
        longList = longList->next;
    }

    // 同时移动长链表和短链表指针,直到找到交点
    while (longList != shortList) {
        longList = longList->next;
        shortList = shortList->next;
    }

    // 返回交点(如果存在)
    return longList;
}

二、141. 环形链表

题目链接:LeetCode—环形链表

题目描述:
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。
注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。

示例 1:
在这里插入图片描述
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:
在这里插入图片描述
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:
在这里插入图片描述
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。


题目解析:
这是经典的快慢指针算法用于检测链表中是否存在环。算法的核心思想是使用两个指针,一个移动速度较慢(每次移动一步),另一个移动速度较快(每次移动两步)。如果链表中存在环,快指针最终会追上慢指针,导致它们相遇。

在遍历过程中,如果快指针能够追上慢指针,就说明存在环。如果没有相遇,而是快指针达到链表的末尾(为NULL),则链表是无环的。

这种算法的时间复杂度为 O(N),其中 N 是链表的长度。这是因为在最坏情况下,快指针将遍历整个链表一次。

代码实现:

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    // 初始化两个指针,slow每次移动一步,fast每次移动两步
    ListNode* slow = head;
    ListNode* fast = head;

    // 遍历链表,直到fast为NULL或fast的下一个节点为NULL
    while (fast != NULL && fast->next != NULL) {
        // slow前进一步
        slow = slow->next;
        // fast前进两步
        fast = fast->next->next;

        // 如果存在环,slow和fast会在某个时刻相遇
        if (slow == fast) {
            // 存在环,返回true
            return true;
        }
    }

    // 遍历完成,没有相遇,说明链表无环
    return false;
}

思考问题:快慢指针的速度有要求吗,会不会存在快指针和慢指针不相遇的情况。

首先说结论,只要有速度差,都可以相遇。

想象一下,快慢指针相遇时,它们在环内,且快指针比慢指针多走了n个环,C是环的大小,我们令快指针的速度为a,慢指针的速度为b。

假设快慢指针走k步,它们相遇。又因为相遇时,快指针比慢指针多走了n个环。我们可以得到 ( a − b ) k = n C (a-b)k = nC (ab)k=nC

我们从题中得知a-b和C,k和n是未知数。易知一定存在整数k和整数n使得等式成立。得出结论,快慢指针一定能在环内相遇。


三、142. 环形链表II

题目链接:LeetCode—环形链表II
经过前两题的铺垫,这题的思路更容易打开了

题目描述:
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。
注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。

示例 1:
在这里插入图片描述
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

示例 3:
在这里插入图片描述
输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。


题目解析:

判断是否有环: 快指针速度设为2,慢指针设为1(为了找入环节点必须这样设置,下面会阐述原因),无环直接返回NULL。

找入环节点: 快指针速度设为2,慢指针设为1的原因在这,想象一下,在极端情况下,快慢指针同时从入环节点出发(可以看作快指针与慢指针相距一个环的距离)。这种情况下,慢指针走了半环,快指针走了一个环;接着慢指针走完剩下半个环来到入环点,这时快指针又走了一个环来到入环点。快慢指针在入环节点相遇了。

在实际情况下,快指针一定先入环,接着慢指针从头节点到达入环节点,这时快慢指针的距离一定小于或等于环。那么可想而知,它们相遇时,慢指针最多走完一次环,快指针在从慢指针入环到它们相遇时也最多走完两次环。 我们设相遇时距离入环节点为X,C时环的大小(X<=C)。

相遇时有等式 2 ( L + X ) = L + n ∗ C + X 2(L+X)=L+n*C+X 2(L+X)=L+nC+X (快指针的路程=L+从头节点到相遇时走了n次环+X,慢指针的路程=L+X)。化简得 L = ( n − 1 ) ∗ X + C − X L=(n-1)*X+C-X L=(n1)X+CX,从公式中我们可以看出,当我们走完L(到达入环节点),等于从距离入环节点的X处开始走,可以走(n-1)次环加上C-X(到达入环节点)。

因此,用两个相同速度的指针,一个从头节点开始走,另一个从相遇点开始走,最终会在入环节点相遇。
在这里插入图片描述
代码实现:

typedef struct ListNode ListNode;

struct ListNode *detectCycle(struct ListNode *head) {
    // 初始化两个指针,slow每次移动一步,fast每次移动两步
    ListNode* slow = head;
    ListNode* fast = head;

    // 遍历链表,直到fast为NULL或fast的下一个节点为NULL
    while (fast && fast->next) {
        // slow前进一步
        slow = slow->next;
        // fast前进两步
        fast = fast->next->next;

        // 如果存在环,slow和fast会在某个时刻相遇
        if (slow == fast) {
            // 相遇点保存在meet中,从链表头开始和meet同时移动,直到再次相遇,即为环的起点
            ListNode* meet = slow;
            while (head != meet) {
                head = head->next;
                meet = meet->next;
            }
            // 返回环的起点
            return meet;
        }
    }

    // 遍历完成,没有相遇,说明链表无环
    return NULL;
}

在这里插入图片描述

如果你喜欢这篇文章,点赞👍+评论+关注⭐️哦!
欢迎大家提出疑问,以及不同的见解。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/150950.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

排查线程阻塞问题

案例代码 package first;import java.util.concurrent.TimeUnit;public class DeadLock {private static volatile Object lock new Object();public static void main(String[] args) {new Thread(() -> {test1();}).start();new Thread(() -> {test2();}).start();}p…

队列的实现---超详细

队列的实现—超详细 文章目录 队列的实现---超详细一、队列的模型二、代码实现以及测试用例①队列初始化②入队③出队④输出队头⑤输出队尾⑥判断队列是否为空⑦队列的长度⑧队列的销毁⑨测试用例 一、队列的模型 队列&#xff1a;只允许在一端进行插入数据操作&#xff0c;在…

Semantic Kernel 学习笔记2

本来想白瞟免费Bing Search API如下&#xff0c;但是报错无法链接利用免费的必应 Bing 自定义搜索打造站内全文搜索_bing_subscription_key-CSDN博客 改成按照官方推荐申请&#xff0c;并在.env文件中添加BING_API_KEY""字段。 1. 打开https://www.microsoft.com/en-…

《QT从基础到进阶·二十七》进度条QProgressBar

ui.ProgressBar.setValue(45); //45% ui.ProgressBar.setMin(0); ui.ProgressBar.setMax(255);0到100分为255份&#xff0c;值为215时&#xff0c;进度条为100/255*215 84% 点击主界面弹出进度条QProgressDialog 常用功能&#xff1a; setWindowFlags(Qt::Dialog | Qt::Cu…

基于象群算法优化概率神经网络PNN的分类预测 - 附代码

基于象群算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于象群算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于象群优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针对PNN神经网络的光滑…

【C语言】自定义类型:结构体、枚举、联合

简单不先于复杂&#xff0c;而是在复杂之后 文章目录 1. 结构体的声明1.1 结构的基础知识1.2 结构的声明1.3 特殊的声明1.4 结构体的自引用1.5 结构体变量的定义和初始化1.6 结构体内存对齐1.7 修改默认对齐数1.8 结构体传参 2. 位段2.1 什么是位段2.2 位段的内存分配2.3 位段的…

解决:java: 错误: 不支持发行版本 5 最有效方法

报错信息如图&#xff1a; 直接上终极方法&#xff1a; 修改配置文件 如图找到settings.xml文件 在标签中间插入如下代码&#xff08;jdk更改为自己电脑上的版本&#xff09; <profile><id>development</id><activation><jdk>11</jdk><…

深入Rust:探索所有权和借用机制

大家好&#xff01;我是lincyang。 今天&#xff0c;我们将一起深入探索Rust语言中的一个核心概念&#xff1a;所有权和借用机制。 这些特性是Rust区别于其他语言的重要特点&#xff0c;它们在内存管理和并发编程中扮演着关键角色。 一、Rust所有权机制 1. 什么是所有权&#x…

USB复合设备构建CDC+HID鼠标键盘套装

最近需要做一个小工具&#xff0c;要用到USB CDCHID设备。又重新研究了一下USB协议和STM32的USB驱动库&#xff0c;也踩了不少坑&#xff0c;因此把代码修改过程记录一下。 开发环境&#xff1a; ST-LINK v2 STM32H743开发板 PC windows 11 cubeMX v6.9.2 cubeIDE v1.13.2 cub…

Google 向中国开发者开放数百份 TensorFlow 资源

Google 的机器学习框架 TensorFlow 自 2015 年开源后&#xff0c;已然成为 AI 领域最受欢迎的框架。 据统计&#xff0c;在广受欢迎的 Python 编程语言在线软件知识库 PyPi 上&#xff0c;TensorFlow 的下载次数已超过 90 万&#xff0c;其中有 15% 来自中国。谷歌官方博客也表…

11.10~11.15置信区间,均值、方差假设检验,正态,t,卡方,F分布,第一第二类错误

置信度&#xff0c;置信区间 给定一个置信度&#xff0c;就可以算出一个置信区间。 如果给的置信度越大&#xff0c;那么阿尔法就越小 给的置信度越小&#xff0c;那么α就越大&#xff0c;那么 考虑精确性&#xff0c;希望区间长度尽可能小&#xff0c;所以是取正态的中间…

Postman的常规断言/动态参数断言/全局断言

近期在复习Postman的基础知识&#xff0c;在小破站上跟着百里老师系统复习了一遍&#xff0c;也做了一些笔记&#xff0c;希望可以给大家一点点启发。 断言&#xff0c;包括状态码断言和业务断言&#xff0c;状态码断言有一个&#xff0c;业务断言有多个。 一&#xff09;常规的…

Python数据容器之(元组)

我们前面所了解的列表是可以修改的&#xff0c;但如果想要传递的信息&#xff0c;不被篡改&#xff0c;列表就不合适了。 元组同列表一样&#xff0c;都是可以封装多个、不同类型的元素在内。 但最大的不同点在于&#xff1a; 元组一旦定义完成&#xff0c;就不可修改 所以…

exce常用

一、冻结 同时冻结行和列 打开一个Excel表格&#xff0c;点击选择需要冻结的行和列交接处对应的单元格&#xff08;例如&#xff1a;需要同时冻结1、2行和A、B列&#xff0c;则选中行列交接对应的C3单元格&#xff09;&#xff09;&#xff0c; 即下一行 和下一列的交接点。 …

虹科方案 | 从概念到生产的自动驾驶软件在环(SiL)测试解决方案

来源&#xff1a;雅名特自动驾驶 虹科方案 | 从概念到生产的自动驾驶软件在环&#xff08;SiL&#xff09;测试解决方案 自动驾驶软件在环&#xff08;SiL&#xff09;测试解决方案 自动驾驶软件在环&#xff08;SiL&#xff09;测试解决方案能够研究和验证高历程实验和恶劣驾…

Xocde 升级15 或者 iOS17报错:

错误&#xff1a; Assertion failed: (false && "compact unwind compressed function offset doesnt fit in 24 bits"), function operator(), file Layout.cpp, line 5758. 翻译&#xff1a; 断言失败&#xff1a;&#xff08;false&&“压缩展开…

计算机网络之网络体系结构

计算机网络体系结构 一、常见的计算机体系结构 1.1 OSI标准以及TCP/IP体系结构 OSI标准失败的原因&#xff1a; OSI的专家们缺乏实际经验&#xff0c;他们在完成OSI标准时没有商业驱动力OSI的协议实现起来过分复杂&#xff0c;而且运行效率很低OSI标准的制定周期太长&#x…

Python中sys模块详解:常用方法与变量

更多Python学习内容&#xff1a;ipengtao.com 大家好&#xff0c;我是涛哥&#xff0c;今天为大家分享 Python中sys模块详解&#xff1a;常用方法与变量&#xff0c;文章2500字&#xff0c;阅读大约8分钟&#xff0c;大家enjoy~~ sys 模块是 Python 标准库中的一个核心模块&…

【C语言 | 数组】C语言数组详解(经典,超详细)

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…

服务名无效。 请键入 NET HELPMSG 2185以获得更多的帮助

遇到的问题是MySQL服务没有。 因为net start 服务名&#xff0c;启动的是win下注册的服务。此时&#xff0c;我系统中并没有注册mysql到服务中。即下面没有mysql服务。 mysqld --install net start mysql