Leetcode刷题之环形链表

这篇具有很好参考价值的文章主要介绍了Leetcode刷题之环形链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

莫等闲,白了少年头,空悲切。                                            --岳飞
目录

1.环形链表

2.环形链表Ⅱ


1.环形链表

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

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

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

实例1:

Leetcode刷题之环形链表

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点

实例2: 

Leetcode刷题之环形链表

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

Leetcode刷题之环形链表

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

做题链接:环形链表
我们要判断这个链表是否有环,这道题我们如何来做呢? 我们还是会使用到双指针,我们定义一个fast快指针,一个slow慢指针。快指针一次走两步,慢指针一次走一步,如果链表有环,那么它们一定会在环中的某个位置相遇,如何理解呢?我们同样使用画图来理解。
Leetcode刷题之环形链表

bool hasCycle(struct ListNode *head) {
    if(head==NULL)
    return false;
    struct ListNode*slow=head,*fast=head;
    while(fast&&fast->next)//这里一定要判断fast->next。如果没环,后面fast->next为空了
    {                      //再次->next,就会出错
        slow=slow->next;//慢指针一次走一步
        fast=fast->next->next;//快指针一次走两步
        if(slow==fast)
        {
             return true;
        }
    }
 return false;
}

这道题还是比较简单的,但是下面的这个题就是这个的加强版,最后要找出进环的第一个位置。

2.环形链表Ⅱ

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

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

不允许修改 链表。

实例1:

Leetcode刷题之环形链表

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

实例2:
 

Leetcode刷题之环形链表

输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

Leetcode刷题之环形链表

输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。

这题同样和上面的起始思想一样,先使用快慢指针找到相遇的位置,但是如何找到环的第一个位置呢?其实这是有一个结论的:两个指针相遇的位置走到进环的位置和头结点走到进环的位置是一样的。 这个是真的很不好理解,需要使用数学公式推导一下。接下来我们就来推导一下。
Leetcode刷题之环形链表

struct ListNode *detectCycle(struct ListNode *head) {
    if(head==NULL)
    return NULL;
    struct ListNode*fast=head,*slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            struct ListNode*cur=head;//头指针的位置
            while(cur!=slow)
            {
                cur=cur->next;
                slow=slow->next;
            }
            return slow;
        }
    }
      return NULL;
}

 文章来源地址https://www.toymoban.com/news/detail-418589.html

到了这里,关于Leetcode刷题之环形链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode刷题:142. 环形链表 II

    题目: 是否独立解决: 否,参考了解题思路解决问题,思考了用快慢指针,栈,统计链表数量定位尾巴节点(因为是环形链表所以是死循环,链表数量用while循环统计不出来)都没解决 解题思路:这题其实和环形链表一样的解题思路,用哈希set将数据都存储进去,如果发现

    2024年01月21日
    浏览(39)
  • Leetcode刷题之复制带随机指针的链表

    生命不是安排,而是追求,人生的意义也许永远没有答案,但也要尽情感受这种没有答案的人生。                                                                                                                     --弗吉尼亚.  伍尔芙         目录 前言:

    2024年02月04日
    浏览(42)
  • Leetcode刷题之回文链表和交换链表中的结点

    竭力履行你的义务,你应该就会知道,你到底有多大的价值。      --列夫.托尔斯泰 目录 🪴一.回文链表 🌻1.快慢指针  🍁2.把值存入数组中,然后使用双指针  🌼二.交换链表中的结点  🍂1.快慢指针 给你一个单链表的头节点  head  ,请你判断该链表是否为回文链表。如

    2024年02月04日
    浏览(50)
  • Leetcode刷题之两两交换链表中的结点和相交链表

    只有把抱怨环境的心情,化为上进的力量,才是成功的保证。       ——罗曼·罗兰 目录 🍉一.相交链表 💐1.双指针 🍍2.计算长度加双指针 🍒二.两两交换链表中的结点  🍌1.迭代  给你两个单链表的头节点  headA  和  headB  ,请你找出并返回两个单链表相交的起始节点

    2024年02月04日
    浏览(32)
  • 【刷题专栏—突破思维】LeetCode 142. 环形链表 II

    前言 :本篇博客将讲解三个OJ题,前两个作为铺垫,最后完成环形链表的节点的寻找 题目链接:LeetCode—相交链表 题目描述: 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节

    2024年02月05日
    浏览(38)
  • 看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题142环形链表II) 2023.4.24

    本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可,撰写本文章主要目的在于记录自己学习体会并分享给大家,全篇并不仅仅是复制粘贴,更多的是加入了自己的思考,希望读完此篇文章能真正帮助到您!!! 力扣题目链接 分析题目: 其实本题目中主

    2024年02月05日
    浏览(49)
  • 【算法刷题之链表篇(1)】

    给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。 1.我们从指针 prev 指向链表的哑节点,随后开始对链表进行遍历。 2.如果当前 cur与 cur.next对应的元素相同,那么我们就需要将 cur 以及所有后面拥有相同元素值

    2024年02月12日
    浏览(33)
  • 【算法刷题之链表篇(2)】

    给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 思路 : 首先写出合并两个链表的代码 : 1.定义两个指针分别位于两个链表的头处,再定义一个哨兵位用于接受元素; 2.两个链表头处的指针开始遍历,并且相互

    2024年02月11日
    浏览(32)
  • 【力扣刷题】回文链表、环形链表、合并两个有序链表

    🐌个人主页: 🐌 叶落闲庭 💨我的专栏:💨 c语言 数据结构 javaEE 操作系统 Redis 石可破也,而不可夺坚;丹可磨也,而不可夺赤。 给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。 首先是要对该链表进行非空校验,若

    2024年02月07日
    浏览(41)
  • 刷题之Leetcode209题(超级详细)

    力扣题目链接(opens new window) https://leetcode.cn/problems/minimum-size-subarray-sum/ 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。 示例: 输入:s = 7, nums = [2,3,1,2,4,3] 输

    2024年04月11日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包