开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> LeetCode每日一练 —— 环形链表问题（面试四连问） -> 正文阅读

[数据结构与算法]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. 动图演示

准备两个指针 fast 和 slow，循环链表；

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. 题目描述

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

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

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

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

2. 思路分析

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

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

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

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

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

那么相遇时：

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

fast 指针走过的节点数： $x + y + n (y + z)$ ，n 为 fast 指针在环内走了 n 圈才遇到 slow 指针， $（ y + z ）$ 为一圈内节点的个数。

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

$(x + y) ? 2 = x + y + n (y + z)$

两边同时消掉一个 $(x + y)$ ，化简得： $x + y = n (y + z)$ ；

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

所以我们要求 x ，将 x 单独放在左边： $x = n (y + z) ? y$ ；

在从 $n (y + z)$ 中提出一个 $(y + z)$ 来，整理公式之后为如下公式： $x = (n ? 1) (y + z) + z$ ；

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

这个公式说明什么呢？

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

当 n 为 1 的时候，公式就化解为 $x = z$ ；

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

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

让 index1 和 index2 同时移动，每次移动一个节点，那么他们相遇的地方就是环形入口的节点。（动图演示👇）
在这里插入图片描述

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

其实这种情况和 n 为 1 的时候 效果是一样的，一样可以通过这个方法找到环形的入口节点，只不过，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）slow 一次走 1 步，fast 一次走 2 步，一定能追上吗？
?
（2）slow 一次走 1 步，fast 一次走 3 步，能追上吗？fast 走 4 步呢？或者 fast 走 n 步呢？能追上吗？
?
针对上面的两个问题作出解答，并证明！