纵然链长千里，心终会在交点重逢

标签：心终 重逢 链长 相遇 fast 链表 slow 节点 指针

公主请阅

• 1. 环形链表I
• • 1.1 题目说明
  • • 示例 1
    • 示例 2
    • 示例 3
  • 1.2 题目分析
  • 1.3 代码部分
  • 1.4 代码分析
• 2. 环形链表 II
• • 2.1 题目说明
  • • 示例 1
    • 示例 2
    • 示例 3
  • 2.2 题目分析
  • 2.2 代码部分
  • 2.4 代码分析
• 3. 两道题的原理
• • 3.1 快慢指针的工作原理
  • 3.2 为什么快慢指针一定会在环内相遇？
  • 3.3 找到环的起始节点
  • 3.4 为什么从头开始走的指针和慢指针会在环的起点相遇？
  • 3.5 总结

1. 环形链表I

题目传送门

---

1.1 题目说明

从图中提取的题目信息如下：

题目描述：
给你一个链表的头节点 head，判断链表中是否有环。

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

返回值：

• 如果链表中存在环，返回 true；否则，返回 false。

示例 1

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

示例 2

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

示例 3

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

提示：

• 链表中的节点数范围是 [0, 10^4]
• -10^5 <= 节点值 <= 10^5

---

1.2 题目分析

题目让我们判断这个链表是不是带环的链表，就是是否循环链表，那么我们怎么进行判断呢？
我们其实可以使用双指针进行问题的解决的
在环形链表（又称循环链表）中，使用快慢指针（也叫龟兔赛跑算法）是为了检测链表是否存在环。其工作原理基于两个指针：一个移动得较慢（慢指针，每次移动一步），另一个移动得较快（快指针，每次移动两步）。通过观察这两个指针在链表中的相对运动情况，可以判断链表是否有环。

快慢指针检测环的原理：

1. 初始状态：

   • 慢指针从链表的头节点开始，每次移动一步；
   • 快指针同样从头节点开始，但每次移动两步。

2. 环形链表的特征：

   • 如果链表中没有环，快指针最终会指向 null，因为它会比慢指针更快到达链表的末尾。
   • 如果链表中存在环，快指针会因为移动速度较快而最终与慢指针相遇。由于快指针每次移动两步，而慢指针只移动一步，在进入环后，快指针会以每次接近慢指针一步的速度追上慢指针。

3. 具体过程：

   • 假设链表中存在一个环，那么快慢指针都会进入这个环。
   • 由于快指针的速度是慢指针的两倍，因此它们会逐渐接近，最终相遇。
   • 当快指针与慢指针相遇时，就可以确认链表中存在环。

关键点：

• 没有环的情况：快指针会比慢指针更快到达链表的末尾，因此不会发生相遇。
• 有环的情况：快指针会追上慢指针，二者在环内的某一点相遇，从而可以判断链表有环。

时间复杂度与空间复杂度：

• 时间复杂度：O(n)，其中 n 是链表的长度。因为快慢指针都只需要遍历一次链表。
• 空间复杂度：O(1)，只使用了两个额外的指针，因此空间复杂度是常数级别。

进一步探讨：
在检测到环之后，如何确定环的起点？

• 当快慢指针在环内相遇后，可以将慢指针重新指向链表头节点，并让快指针留在原地。
• 之后，两个指针都每次移动一步，它们再次相遇的地方即是环的起点。

通过这种方法，我们不仅能够检测到环，还能够找到环的起点，整个过程高效且无需额外的空间。

---

1.3 代码部分

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode  ListNode;
bool hasCycle(struct ListNode *head)
{
    ListNode*slow=head;
    ListNode*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)//快慢指针相遇了
        {
            return true;
        }
    }
    //循环结束两个指针都没相遇
    return false;
}

---

1.4 代码分析

我们先创建两个指针，fast和slow进行遍历链表的操作
我们利用while循环进行遍历的操作。条件是fast&&fast->next
两个条件是不能换位置的，因为如果我们让fast->next放在前面的话，但是fast是空的话，那么这个就会出现问题了。所以我们得先判断fast是不是空的，再判断下一个节点是不是空的
然后我们在循环里面进行两个指针的移动操作，每次一步，然后并且进行判断，如果这个链表带环的话，那么快慢指针是会相遇的，如果相遇了，指针相等的话，那么肯定这个链表就是带环链表了

---

2. 环形链表 II

题目传送门

---

2.1 题目说明

这道题是《环形链表 II》的问题，主要目的是找到链表中环的起始节点。如果链表中存在一个环，则返回环的第一个节点；如果链表无环，则返回 null。题目不允许修改链表。

题目内容总结

• 给定一个链表的头节点 head，需要判断该链表是否存在环，并返回环的起始节点。
• 链表中的某个节点的 next 指针会指向之前某个节点，形成环。
• 题目中的 pos 是链表尾部节点连接到的索引位置（从0开始），用来标识环的实际存在位置，如果 pos = -1 则表示链表中没有环。

示例 1

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

示例 2

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

示例 3

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

关键点

1. 是否存在环：通过遍历链表来判断是否存在环。
2. 找到环的入口：如果存在环，返回环的起始节点。
3. 双指针法：通常可以使用快慢指针（Floyd判圈算法）来判断是否存在环并找出环的入口节点。

---

2.2 题目分析

题目要求我们先判断当前的链表是不是带环的，如果带环的话，我们再将入环的第一个节点进行返回了
那么我们前面可以通过快慢指针来判断当前的链表是否带环，但是我们怎么将这个入环的第一个节点返回了呢？
我们可以先创建一个指针指向我们的头结点，等我们的快慢指针相遇了，然后我们就让指向头结点的这个指针和慢指针一起走，直到我们的头结点指针遇到了慢指针我们就停下
那么当这两个指针相遇的时候我们就将当前的位置直接返回就行了，当前的位置就是我们所需要的入环节点处

---

2.2 代码部分

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 //返回入环的节点
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head)
{
    //快满指针
    ListNode *slow=head;
    ListNode *fast=head;

    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)//相遇了，在环的节点处
        {
            //我们定义一个指针从头节点走到当前的环的节点处
            ListNode *pcur=head;
            while(pcur!=slow)
            {
                pcur=pcur->next;
                slow=slow->next;
            }
            //此时我们跳出循环说明了两个指针已经相等了
            return pcur;
        }
    }
    //跳出这个循环的话就说明我们没找到环的节点
    return NULL;
}

//我们先使用快满指针走到两个指针的相遇节点
//然后我们让慢指针和头节点的指针一起运动，直到两个指针相遇的话，就说明我们的相遇点就是入环处，那么这个位置就是我们要找的位置了

---

2.4 代码分析

我们先创建快慢指针，利用快慢指针进行带环链表的判断，如果不带环我们就返回NULL，如果带环的话我们继续进行后面的判断操作，我们创建一个指针pcur指向当前的头结点，然后我们利用while循环，让慢指针和pcur一起进行链表的遍历操作，这个循环的条件是我们的pcur和慢指针相遇了，然后我们将此时的pcur进行返回，因为此时的pcur就是我们的带环节点处

3. 两道题的原理

这个算法的核心原理是 Floyd 判圈算法（也叫快慢指针法），它用于检测链表中是否存在环以及找到环的入口。下面是详细的原理解释：

3.1 快慢指针的工作原理

快慢指针法通过使用两个指针来遍历链表：

• 慢指针（slow）：每次只移动一步。
• 快指针（fast）：每次移动两步。

假设链表存在一个环：

• 在没有环的情况下，fast 指针会先到达链表的末尾，并且链表中不存在环，所以返回 NULL。
• 如果链表中有环，fast 指针将会比 slow 指针快两倍，这意味着它最终会在环中“追上”慢指针，二者会在环中的某个节点相遇。这个相遇点并不一定是环的起点，而是环中的某个位置。

3.2 为什么快慢指针一定会在环内相遇？

在环内，快慢指针的相对速度是 1，因为 fast 每次走两步，slow 每次走一步，因此 fast 每次比 slow 多走一步。如果我们将环视作一个圆形跑道，快指针以比慢指针快一倍的速度跑步，慢指针始终在前，快指针始终在后。在这个环中，不管它们从哪里开始，快指针都会最终追上慢指针并与之相遇。

3.3 找到环的起始节点

当快慢指针在环中相遇后，可以确定链表中确实存在环。接下来，我们要找的是环的起点。这时，我们采取以下步骤：

1. 我们将其中一个指针（slow）保留在相遇点，另一个指针（pcur）从链表的头节点 head 开始，同时两者每次各走一步。
2. 由于两个指针的移动速度相同，并且它们一定会在环的起始节点相遇，所以当 pcur 和 slow 再次相遇时，它们就处于环的起始节点。

3.4 为什么从头开始走的指针和慢指针会在环的起点相遇？

为了理解这个过程，我们需要用到一些数学分析。

设链表的头节点到环的起点的距离为 a，环的起点到快慢指针相遇点的距离为 b，环的总长度为 L，即环的长度是 L。

• 当快慢指针相遇时，快指针已经走了 a + b + nL 步，慢指针走了 a + b 步（n 表示快指针在环内完整绕行的次数）。
• 因为快指针每次走两步，慢指针每次走一步，所以 fast 走的步数是 slow 的两倍：

                                         2(a+b)=a+b+nL

简化得出：

                                              a+b=nL

即从头节点到环的起点的距离 a，加上从环起点到相遇点的距离 b，正好等于环的整数倍。这意味着，如果我们从头节点 head 开始，一个指针每次走一步，而 slow 从相遇点继续走，他们将会在环的起点相遇。

3.5 总结

• 第一步：快慢指针在环中相遇，证明链表有环。
• 第二步：从头节点和相遇点分别同时移动一个新指针和 slow，最终它们会在环的起始节点相遇，进而找到环的入口。

这就是为什么 Floyd 判圈算法 能在 O(n) 时间复杂度和 O(1) 空间复杂度下，既能检测链表是否有环，又能找到环的起始节点。

如果你需要更详细的图示或代码解析，随时可以告诉我！

标签：心终,重逢,链长,相遇,fast,链表,slow,节点,指针
From： https://blog.csdn.net/2301_80863610/article/details/143063205