首页 > 其他分享 >LeetCode Hot100刷题记录-141.环形链表

LeetCode Hot100刷题记录-141.环形链表

时间:2024-09-11 11:02:51浏览次数:12  
标签:head slow 141 fast next 链表 Hot100 指针

给你一个链表的头节点 head ,判断链表中是否有环。

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

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

思路!
最常见的算法是使用 快慢指针法,也叫龟兔赛跑算法(Floyd's Cycle Detection Algorithm)。这个算法的核心思路是利用两个指针:

  • 慢指针 (slow) 每次只移动一步。
  • 快指针 (fast) 每次移动两步。
  • 如果链表有环,那么快指针和慢指针最终会在环中相遇。如果链表没有环,那么快指针会在链表末端(null)结束。
var hasCycle = function(head) {
    if (!head || !head.next){
        return false;
    }
    let fast = head.next;
    let slow = head;
    while(fast !== slow){
        if(!fast || !fast.next){
        return false;
    }
        fast = fast.next.next;
        slow = slow.next;
    }
    return true;
};

✨为什么 fast 要从 head.next 开始
如果 fast 和 slow 都从 head 开始(也就是链表的起点),在进入循环的第一步时,fast 和 slow 可能立刻相等,因为它们都指向同一个节点,即链表的头节点。这种情况下,算法会误判链表是有环的,尽管实际上链表可能没有环。
为了避免这个问题,我们让 fast 指向 head.next,也就是让快慢指针一开始分开一步。这样在进入循环时,快慢指针至少不会在起点相遇,只有当链表真的有环时,fast 才有机会通过它的“快速度”在后续的某个点追上 slow。

适用场景
快慢指针是一种非常高效且常用的链表问题处理方式,除了环形链表和回文链表,还可以应用在:

  • 寻找链表的中点。
  • 寻找链表的倒数第 k 个节点。
  • 判断链表长度的奇偶性。

标签:head,slow,141,fast,next,链表,Hot100,指针
From: https://www.cnblogs.com/gardenOfCicy/p/18407281

相关文章

  • LeetCode Hot100刷题记录-234.回文链表
    题目:给你一个单链表的头节点head,请你判断该链表是否为回文链表。如果是,返回true;否则,返回false。PS:回文序列是向前和向后读都相同的序列。解题思路:遍历链表,将每个元素存放入一个新的数组中。遍历完成后,再用两个指针前后遍历数组来判断两个数字是否相等。/***Def......
  • c语言--力扣简单题目(删除排序链表中的重复元素)讲解
    题目如下:给定一个已排序的链表的头head,删除所有重复的元素,使每个元素只出现一次。返回已排序的链表。示例1:输入:head=[1,1,2]输出:[1,2]示例2:输入:head=[1,1,2,3,3]输出:[1,2,3]提示:链表中节点数目在范围[0,300]内-100<=Node.val<=100题目数据保......
  • 重头开始嵌入式第三十七天(数据结构 链表)
    单向链表单向链表是一种常见的数据结构。一、结构组成-节点:单向链表由多个节点组成。每个节点包含两个部分,一个是存储数据的部分,可以存储各种类型的数据,如整数、字符、结构体等;另一个是指向下一个节点的指针,用于连接链表中的各个节点。-头指针:链表有一个特殊的指针称为头......
  • 数据结构—链表
    一:链表1、数组是连续的内存空间;而链表可以不一定是连续的内存空间2、单端链表;从前一个元素指向后一个元素3、链表的功能(1)访问o(n):数组是通过下表或者索引访问元素;链表是通过next指针以此递归的进行查询判断(2)搜索o(n):从头部遍历;知道找到位置(3)插入o(1):(4)删除o(1):4、特......
  • 每日算法随笔:反转链表 II
    明白了!下面我将基于你给的两种方法来详细解释题解,并展示每一步的变化过程。题解:反转链表II这道题要求我们反转链表中从第left个节点到第right个节点的部分,返回反转后的链表。我们会使用两种方法:递归和迭代。示例解析示例1:输入:head=[1,2,3,4,5],left=2,ri......
  • 每日算法随笔:反转链表
    题解:反转链表这道题目要求我们将一个单链表进行反转,返回反转后的链表。链表的反转可以通过迭代和递归两种方法来实现。下面我们将详细解释这两种方法,并通过例子演示每一步的变化过程。方法一:迭代法思路:我们用三个指针来完成链表的反转:prev表示前一个节点,curr表示当前节......
  • Java-实现双向环形链表
            双向链表是一种常用的数据结构,其特点是每个节点不仅包含数据,还持有指向前一个节点和后一个节点的指针。与普通双向链表不同的是,它的哨兵节点的prev指向最后一个元素,而最后一个元素的next指向哨兵。        具体双向普通链表可以参考我的上篇文章,这里......
  • [Python手撕]排序链表
    #Definitionforsingly-linkedlist.#classListNode:#def__init__(self,val=0,next=None):#self.val=val#self.next=nextclassSolution:defsortList(self,head:Optional[ListNode])->Optional[ListNode]:def......
  • 数据结构—单链表的基本操作
    目录1.单链表的初始化2.求表长操作3.按序号查找结点4.按值查找表结点5.插入结点操作6.删除结点操作7.头插法建立单链表8.尾插法建立单链表1.单链表的初始化 带头结点: boolInitList(LinkList&L){       //带头结点的单链表的初始化  L=(......
  • C ++ 从单链表到创建二叉树到二叉树的遍历(结构体)
    首先我们要了解二叉树的数据结构是什么,本质上二叉树是一个有两个节点的链表,我们先了解的单链表的相关定义单链表创建一个朴素的单链表#include<iostream>usingnamespacestd;structNode{intval;Node*next;Node(intx):val(x),next(nullptr){}......