• LeetCode每日一练 —— 环形链表问题(面试四连问)


    🌟 前言

    Wassup guys!我是Edison 😎

    今天是 LeetCode 上的两道题: 141. 环形链表142. 环形链表 II

    Let’s get it!

    在这里插入图片描述



    判断链表是否有环

    1. 题目描述

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

    示例 1:
    在这里插入图片描述

    示例 2:
    在这里插入图片描述

    示例 3:
    在这里插入图片描述

    2. 思路分析

    这道题的思路很简单,还是用 快慢指针

    每当慢指针 slow 前进一步,快指针 fast 就前进两步。
     
    如果 fast 最终遇到空指针,说明链表中没有环;
     
    如果 fast 最终和 slow 相遇,那肯定是 fast 超过了 slow 一圈,说明链表中含有环。

    注意,如果链表没有环:

    链表如果是 奇数 个,那么 slow 走一步,fast 走两步的话,那么 fast 一定走到 尾节点 ,所以终止循环的条件就是 fast->next != NULL
     
    链表如果是 奇数 个,那么 slow 走一步,fast 走两步的话,那么 fast 一定走到 NULL 的位置,所以终止循环的条件就是 fast != NULL

    3. 动图演示

    准备两个指针 fastslow,循环链表;

    slow 指针初始也指向 head,每次循环向前走一步;

    fast 指针初始指向 head,每次循环向前两步;

    如果没有环,则快指针会抵达终点,如果有环,那么快指针会追上慢指针(动图演示👇)
    在这里插入图片描述

    4. 代码实现

    接口代码

    bool hasCycle(struct ListNode *head) {
        // 快慢指针初始化指向 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;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    提交结果
    在这里插入图片描述

    返回链表入环的第一个结点

    1. 题目描述

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

    示例 1:
    在这里插入图片描述

    示例 2:
    在这里插入图片描述

    示例 3:
    在这里插入图片描述

    2. 思路分析

    这已经不是一道简单的代码题了,确切的来说,是 数学公式推导 + 逻辑结合 的一道题。
     
    为什么要这样呢?这里简单说一下其中的原理。

    通过上面的第一道题,已经学会了判断链表是否有环了,那么接下来要找这个环的入口了。

    假设从 头结点 到环形 入口节点 的节点数为 x

    环形 入口节点fast 指针与 slow 指针 相遇节点 节点数为 y

    相遇节点 再到环形 入口节点 的节点数为 z。 (如图所示👇)
    在这里插入图片描述

    那么相遇时:

    slow 指针走过的节点数为:: x + y x + y x+y

    fast 指针走过的节点数: x + y + n ( y + z ) x + y + n (y + z) x+y+n(y+z)nfast 指针在环内走了 n 圈才遇到 slow 指针, ( y + z ) (y+z) y+z为一圈内节点的个数。

    因为 fast 指针是一步走两个节点,slow 指针一步走一个节点, 所以 f a s t 指针走过的节点数 = s l o w 指针走过的节点数 ∗ 2 fast 指针走过的节点数 = slow 指针走过的节点数 * 2 fast指针走过的节点数=slow指针走过的节点数2,也就是👇

    ( x + y ) ∗ 2 = x + y + n ( y + z ) (x + y) * 2 = x + y + n (y + z) (x+y)2=x+y+n(y+z)

    两边同时消掉一个 ( x + y ) (x+y) (x+y),化简得: x + y = n ( y + z ) x + y = n (y + z) x+y=n(y+z)

    因为我们要找环形的入口,那么要求的是 x,因为 x 表示 头结点环形入口节点 的距离。

    所以我们要求 x ,将 x 单独放在左边: x = n ( y + z ) − y x = n (y + z) - y x=n(y+z)y

    在从 n ( y + z ) n(y+z) n(y+z) 中提出一个 ( y + z ) (y+z) (y+z) 来,整理公式之后为如下公式: x = ( n − 1 ) ( y + z ) + z x = (n - 1) (y + z) + z x=(n1)(y+z)+z

    注意这里 n 一定是大于等于 1 的,因为 fast 指针 至少要多走一圈 才能相遇 slow 指针。

    这个公式说明什么呢?

    先拿 n1 的情况来举例,意味着 fast 指针在环形里转了一圈之后,就遇到了 slow 指针了。

    n1 的时候,公式就化解为 x = z x = z x=z

    这就意味着,从头结点出发一个指针,从相遇节点也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是环形入口的节点。

    也就是在相遇节点处,定义一个指针 index1,在头结点处定一个指针 index2

    index1index2 同时移动,每次移动一个节点, 那么他们相遇的地方就是环形入口的节点。 (动图演示👇)
    在这里插入图片描述

    那么 n 如果大于 1 是什么情况呢?就是 fast 指针在环形转 n 圈之后才遇到 slow 指针。

    其实这种情况和 n1 的时候 效果是一样的,一样可以通过这个方法找到 环形的入口节点,只不过,index1 指针在环里 多转了 (n-1) 圈,然后再遇到 index2,相遇点依然是环形的入口节点。

    3. 简化思路

    我们假设 快慢指针相遇 时,慢指针 slow 走了 k 步,那么快指针 fast 一定走了 2k 步(如图所示👇)
    在这里插入图片描述

    fast 一定比 slow 多走了 k 步,这多走的 k 步其实就是 fast 指针在环里转圈圈,所以 k 的值就是环长度的「整数倍」。

    假设 相遇点环的起点 的距离为 m,(见下图👇)那么 环的起点 距头结点 head 的距离为 k - m,也就是说如果从 head 前进 k - m 步就能到达环起点。

    如果从相遇点继续前进 k - m 步,也恰好到达环起点。因为结合上图的 fast 指针,从相遇点开始走 k 步可以转回到相遇点,那走 k - m 步肯定就走到环起点了(如图所示👇)
    在这里插入图片描述
    所以,只要我们把快慢指针中的任一个重新指向 head,然后两个指针同速前进,k - m 步后一定会相遇,相遇之处就是环的起点了

    4. 代码实现

    接口代码

    struct ListNode *detectCycle(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) {
                struct ListNode* meet = slow;
                while (meet != head) {
                    meet = meet->next; // 一个指针从出发点开始走
                    head = head->next; // 一个指针从出发点开始走  
                }
                // meet和head相等时,返回的就是入口点
                return meet;
            }
        }
        // 链表不带环
        return NULL;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    提交结果
    在这里插入图片描述

    扩展追问

    这道题的实现很简单,但是这里会有几个扩展问题,需要证明!

    (1)slow 一次走 1 步,fast 一次走 2 步,一定能追上吗?
     
    (2)slow 一次走 1 步,fast 一次走 3 步,能追上吗?fast4 步呢?或者 fastn 步呢?能追上吗?
     
    针对上面的两个问题作出解答,并证明!

    🍑 问题一

    slow 一次走 1 步,fast 一次走 2 步,一定能追上吗?

    假设链表带环,两个指针最后都会进入环,快指针先进环慢指针后进环

    当慢指针刚进环时,可能就和快指针相遇了,假设 快指针慢指针 之间的距离为 N

    在他们移动的过程中,快指针往前走两步,慢指针走一步,此时,两个指针每移动一次,之间的距离就缩小 1 步,直到缩小为 0,那么就意味着他们相遇了,所以不会出现每次刚好是套圈的情况,

    因此,在慢指针走到一圈之前,快指针肯定是可以追上慢指针的,即相遇。
    在这里插入图片描述

    🍑 问题二

    slow 一次走 1 步,fast 一次走 3 步,能追上吗?fast4 步呢?或者 fastn 步呢?能追上吗?

    在他们前进的过程中,快指针 每次走 3 步,慢指针 每次走 1 步,此时 快指针 肯定 先进环慢指针后进环

    假设 慢指针 进环时,快指针慢指针 之间的距离为 N,又因为 快指针 每次走 3 步,慢指针 每次走 1 步,所以每走一次,他们之间的距离就缩小 2

    此时要分 种情况:

    1、如果 N 为偶数,那么他们之间的距离最终会缩小 0,也就是相遇。

    2、如果 N 为奇数,那么他们之间的会减到 1,然后减到 负1,减到 负1 也就意味着他们之间的距离又变成了 C - 1C 是环的周长),此时又分为 2 种情况;

    2.1、若 C 为奇数,则 C - 1 为偶数,因为他们之间的距离一次缩小 2,所以他们还是会相遇;

    2.2、若 C 为偶数,则 C - 1 为奇数,也就是说他们之间的距离还是奇数,那么他们永远都不会相遇。

    在这里插入图片描述

    总结:

    当慢指针走一步,快指针走三步时。
     
    慢指针进环时快指针 之间的距离为 奇数,并且环的周长恰好为 偶数,那么他们会一直在环里面打转转,永远不会相遇。

  • 相关阅读:
    【论文精读】CONTAINER: Few-Shot Named Entity Recognition via Contrastive Learning
    YOLO目标检测——火焰检测数据集+已标注xml和txt格式标签下载分享
    深入理解JavaScript中的事件冒泡与事件捕获
    主机基本安全加固
    高等教育心理学:学生的认知发展
    力扣(LeetCode)134. 加油站(C++)
    学习--RTOS速读
    【408数据结构与算法】—串和BF算法(二十四)
    G2plot 面积图Area更新空数据,页面渲染不彻底
    Python列出一个文件夹下的所有文件tif文件
  • 原文地址:https://blog.csdn.net/m0_63325890/article/details/126024091