首页 > 其他分享 >Leetcode 141. 环形链表(超详图解,解析过程)

Leetcode 141. 环形链表(超详图解,解析过程)

时间:2024-08-07 15:24:13浏览次数:19  
标签:head slow 141 超详 fast next 链表 指针

141.环形链表

点击跳转leetcode原题
给你一个链表的头节点 head ,判断链表中是否有环。

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

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
提示:

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

题解(快慢指针)

bool hasCycle(struct ListNode *head) {
    struct ListNode*slow=head;//慢指针
    struct ListNode*fast=head;//快指针
    while(fast&&fast->next)
    {
        slow=slow->next;//慢指针走一步
        fast=fast->next->next;//快指针走两步
        if(slow==fast)
        {
            return true;
        }
    }
    return false;
}

题解原理

定义一个慢指针和一个快指针在头节点,慢指针走一步,快指针走两步,如果链表存在环时,快指针会在慢指针进入环前不断地循环,直到慢指针进入环后与快指针相遇。同理,若快指针走到NULL且快慢指针并没有相遇则说明该链表不是环形链表。

怎么证明环形链表内快慢指针一定会相遇呢?

定义一个快指针和一个慢指针。
在这里插入图片描述
快指针走一步,慢指针走两步。
在这里插入图片描述
若链表内有环,快指针会比慢指针先进入环并在慢指针进环前不断在环里走下去。
但慢指针进入环,快指针开始追击,设慢指针进环时两指针距离为N,环长度为C,快慢指针速度差为一。
在这里插入图片描述
所以N步后两指针距离为0,两指针相遇
在这里插入图片描述

那当慢指针走一步,快指针走三步时呢?

假设慢指针进环前走的长度为L,slow进环时,fast和slow的距离是N,环长度为C。X为快指针在慢指针进环前绕的圈数。
在这里插入图片描述
当慢指针进环时:
慢指针走过的距离为:L
快指针走过的距离为:L+X*C+C-N

快指针的速度是慢指针的三倍:3L=L+X*C+C-N
由上式推出得:2L=(X-1)C-N
等号左边一定是偶数(2与任意整数相乘结果都是偶数),故,当C与N都是偶数时等式成立。

标签:head,slow,141,超详,fast,next,链表,指针
From: https://blog.csdn.net/Whisper_long/article/details/140950764

相关文章

  • 每日一题:Leetcode-24 两两交换链表中的节点
    力扣题目解题思路java代码力扣题目:给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。示例1:输入:head=[1,2,3,4]输出:[2,1,4,3]示例2:输入:head=[]输出:[]示例3:输入:head=[1]......
  • 超详细明了的C语言函数递归,望周知。(包含求n的阶乘顺序打印⼀个整数的每⼀位求第n个斐
    1.递归是什么?递归是学习C语⾔函数绕不开的⼀个话题,那什么是递归呢?递归其实是⼀种解决问题的⽅法,在C语⾔中,递归就是函数⾃⼰调⽤⾃⼰。写⼀个史上最简单的C语⾔递归代码#include<stdio.h>intmain(){printf......
  • 203. 移除链表元素 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满
    在链表中,每个节点都有一个指向下一个节点的指针。删除一个节点的本质是将前一个节点的指针指向要删除节点的下一个节点,从而跳过要删除的节点。以下是详细解释为什么以及如何这样做:1.**链表的结构**:  一个链表节点包含两个部分:存储的数据和指向下一个节点的指针。  ``......
  • basic_pentesting_2靶场实战【超详细】
    下载链接:https://download.vulnhub.com/basicpentesting/basic_pentesting_2.tar.gz一、靶场配置网卡配置为nat二、主机探测与端口扫描nmap192.168.121.0/24 开放了22、80、31337端口nmap192.168.121.188-p--A-sV-Pn 访问80web服务 提示跟随白色兔子f12......
  • 数据结构——链表
    数据结构——链表概念代码实现节点申请节点空间尾插头插尾删头删查找在指定位置之前插入数据在指定位置之后插入数据删除pos节点删除pos后一节点销毁链表概念链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的......
  • 网络安全学习路线+自学笔记(超详细) 自学网络安全看这一篇就够了
    一、什么是网络安全网络安全是一种综合性的概念,涵盖了保护计算机系统、网络基础设施和数据免受未经授权的访问、攻击、损害或盗窃的一系列措施和技术。经常听到的“红队”、“渗透测试”等就是研究攻击技术,而“蓝队”、“安全运营”、“安全运维”则研究防御技术。作为一......
  • 数据结构----链表
        接下来我打算更新数据结构相关方面的知识,使用的语言是Java,但是其中的逻辑和思路并不影响。如果感兴趣可以关注合集。    希望大家看完之后可以自己去手敲实现一遍,同时在最后我也列出一些基本和经典的题目,可以尝试做一下。大家也可以自己去力扣或者洛谷牛客......
  • 【链表OJ】常见面试题 2
    文章目录1.[链表分割](https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking)1.1题目要求1.2哨兵位法2.[链表的回文结构](https://www.nowcoder.co......
  • 【ceph】手动编译14.2.22 ceph版本---超详细版本,生产可用
      本站以分享各种运维经验和运维所需要的技能为主《python零基础入门》:python零基础入门学习《python运维脚本》: python运维脚本实践《shell》:shell学习《terraform》持续更新中:terraform_Aws学习零基础入门到最佳实战《k8》暂未更新《docker学习》暂未更新《ceph学......
  • 【数据结构】反转链表,合并有序链表,有无环的判断
    前言:小编在上期进行了单链表的模拟,这期接上期进行单链表相关题目讲解1.反转单链表 1.1.题目题目来源:.-力扣(LeetCode)给定一个单链表,实现单链表的反转,图示如下:1.2.解题思路首先在反转时,应该用到头插法,即将第一个后面的元素逐步插入到头结点之前,这里头结点每次要进......