当前位置: 首页 > news >正文

关于如何找环形链表的入环点

目录

  • 一、判断一个链表是否有环
  • 二、找到链表入环的第一个节点

一、判断一个链表是否有环

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

用快慢指针,慢指针一次往后走一步,快指针一次往后走两步。这样快指针会比慢指针先入环,当慢指针入环被快指针追上时,说明这是一个环形链表,当快指针为空或者指向空时,说明这不是环形链表,返回NULL。

在这里插入图片描述
为什么肯定slow 和 fast一定会相遇呢?我们假设当slow入环时,fast到slow的距离为N。
在这里插入图片描述
而slow 每次往前走一步,fast 每次往前走两步,那么它们的距离是逐渐递减的。
在这里插入图片描述
最后它们之间的距离为 0 时,它们就相遇了。

那问题来了,如果fast 一次走三步,四步,五步,它能不能在环中与slow相遇呢? 我们假设fast一次走三步。
fast到slow的距离继续为N
在这里插入图片描述

slow 一次走一步, fast一次走三步 , 那么N是每次少2
在这里插入图片描述
此时会出现两者情况,一种情况是相遇了,还有一种情况是没相遇。
当没相遇的时候,fast已经跑到了 slow的前面,也就是它们此时的距离是-1。
在这里插入图片描述
设这个环的长度为C,所以它们的距离 N 此时是等于 C-1的。而因为fast一次是走三步的,所以N每次会-2。 当N等于0时它们才会相遇,这也就意味,C-1 如果是偶数,那么它们才会相遇,如果C-1 是奇数,那它们永远不会相遇。所以,fast 一次走两步,它一定会和slow在环里面相遇,slow不用走完一圈。如果fast一次走3,4,5…n步,那么是有可能永远不会与slow相遇的。

代码如下:

bool hasCycle(struct ListNode *head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;

    //如果fast为空或者指向空,说明不是环形链表
    while(fast && fast->next)
    {
        //慢指针一次走一步,快指针走两步
        fast = fast->next->next;
        slow = slow->next;

        //如果fast 与 slow 相遇,说明是环形链表
        if(fast == slow)
        {
            return true;
        }
    }
    //出了循环,说明不是环形链表
    return false;
}

题目链接

二、找到链表入环的第一个节点

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

判断了一个链表是否有环之后,那么如何找到链表入环的第一个节点呢?我们设链表头节点到入环的第一个节点为L。
在这里插入图片描述
我们再设 入环的第一个节点,到slow 与fast相遇的节点的距离为X。
在这里插入图片描述
那么slow 走的距离是 L + X
设圆的长度为C
那么fast走的距离是 L + NC + X
N代表走的圈数,因为当环长度很小,而L长度非常大的时候,slow 入环时,fast 不可能只走一圈,一圈是极端情况,这样我们就可以推导出。
2(L + X ) = L + N
C +X
L + X = N * C
L = N * C - X
L = (N-1) *C + C - X
而N - 1 是 fast走的圈数,我们可以省掉
所以 L = C - X
在这里插入图片描述
代码:

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow , *fast;
    slow = fast = head;
    while(fast && fast->next)
    {
       
        fast = fast->next->next;
        slow = slow->next;

         if(fast == slow)
        {
            //保存相遇节点
            struct ListNode* MeetNode = slow;
            struct ListNode* NewHead = head;
            //相遇点和头节点同时走
            while(MeetNode != NewHead)
            {
                MeetNode =  MeetNode->next;
                NewHead =   NewHead->next;
            }
            return MeetNode;
        }
    }
    return NULL;
}

当然,这题还有第二种方法,不过容易理解,实现起来可能有点困难。
我们可以把相遇节点的下一个节点,作为一个新链表的头节点,而上一个节点作为两个链表的尾节点。而这俩个相交的节点,就是入环的第一个节点
在这里插入图片描述
至于如何找到两个链表的交点,上一篇博客第八题有说明,传送地址

所以第二种方法,我们只需要找到它们的newhead和head的相交节点就可。

代码

struct ListNode *detectCycle(struct ListNode *head) {
        struct ListNode* slow , *fast;
        slow = fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            //如果俩节点相遇
            if(slow == fast)
            {
                //新节点为相遇的下一个节点
                struct ListNode* NewHead = slow->next;
                struct ListNode* OldHead = head;
                //求出新节点 和 原头节点 到 尾节点(slow)的长度 
                int lenNew = 1;
                int lenOld = 1;
                while(NewHead != slow)
                {
                    NewHead = NewHead->next;
                    lenNew++;
                }

                while(OldHead!= slow)
                {
                    OldHead = OldHead->next;
                    lenOld++;
                }
                //相差多少个长度
                int gap = abs(lenOld - lenNew);
                //找到较长和较短的链表
                struct ListNode* LongList = head;
                struct ListNode* ShortList = slow->next;
                if(lenOld < lenNew)
                {
                    LongList = slow->next;
                    ShortList = head;
                }
                //让长节点先走gap次
                while(gap--)
                {
                    LongList = LongList->next;
                }
                //然后俩个节点同时走
                while(LongList != ShortList)
                {
                    LongList = LongList->next;
                    ShortList = ShortList->next;
                }
                //此时就是相交节点
                return ShortList;
            }

        }
    return NULL;
}

题目链接

相关文章:

  • 下班路上捡了一部手机,我用8年开发知识主动找到了失主
  • 【Linux系统】第三篇:Linux中软件包管理器yum的使用
  • Bootstrap学习(十一)
  • 学生HTML个人网页作业作品:基于HTML实现教育培训机构网站模板毕业源码(8页)
  • 作为前端你还不懂MutationObserver?那Out了
  • 2021 年河南省中等职业教育技能大赛“网络安全”项目比赛任务书解析教程
  • 【目标检测】Faster R-CNN论文代码复现过程解读(含源代码)
  • rpm包常用命令指南
  • 15.前端笔记-CSS-PS切图
  • 网站变灰代码如何让网页变灰
  • 实用调试技巧
  • Python图像处理【3】Python图像处理库应用
  • Android编写一个视频监控App
  • C++语法——map与set的封装原理
  • 搭建gataway鉴权流程
  • 【159天】尚学堂高琪Java300集视频精华笔记(128)
  • 【EOS】Cleos基础
  • 【跃迁之路】【669天】程序员高效学习方法论探索系列(实验阶段426-2018.12.13)...
  • CentOS从零开始部署Nodejs项目
  • egg(89)--egg之redis的发布和订阅
  • iOS小技巧之UIImagePickerController实现头像选择
  • JavaScript函数式编程(一)
  • js 实现textarea输入字数提示
  • python docx文档转html页面
  • Python学习之路13-记分
  • Python语法速览与机器学习开发环境搭建
  • SegmentFault 社区上线小程序开发频道,助力小程序开发者生态
  • Travix是如何部署应用程序到Kubernetes上的
  • Unix命令
  • vue-loader 源码解析系列之 selector
  • 第三十一到第三十三天:我是精明的小卖家(一)
  • 翻译:Hystrix - How To Use
  • 聚类分析——Kmeans
  • 可能是历史上最全的CC0版权可以免费商用的图片网站
  • 利用jquery编写加法运算验证码
  • 前端每日实战:61# 视频演示如何用纯 CSS 创作一只咖啡壶
  • 双管齐下,VMware的容器新战略
  • 一道面试题引发的“血案”
  • 字符串匹配基础上
  • (1)安装hadoop之虚拟机准备(配置IP与主机名)
  • (2)关于RabbitMq 的 Topic Exchange 主题交换机
  • (DenseNet)Densely Connected Convolutional Networks--Gao Huang
  • (二)斐波那契Fabonacci函数
  • (附源码)springboot课程在线考试系统 毕业设计 655127
  • (附源码)计算机毕业设计SSM基于java的云顶博客系统
  • (论文阅读11/100)Fast R-CNN
  • (收藏)Git和Repo扫盲——如何取得Android源代码
  • (原創) 如何讓IE7按第二次Ctrl + Tab時,回到原來的索引標籤? (Web) (IE) (OS) (Windows)...
  • .gitignore文件_Git:.gitignore
  • .Net 4.0并行库实用性演练
  • .NET CF命令行调试器MDbg入门(一)
  • .NET Core实战项目之CMS 第十二章 开发篇-Dapper封装CURD及仓储代码生成器实现
  • .Net Framework 4.x 程序到底运行在哪个 CLR 版本之上
  • .net 简单实现MD5
  • .NET使用存储过程实现对数据库的增删改查