让我挠头的计算机难题（链表带环）

在这里插入图片描述

前言

在解决环形链表的问题中，百分之九十的题目要用到快慢指针之一思维；

一.环形链表

环形链表 根据数学推理可得，若链表中存在环，快指针一定会追上慢指针；

在这里插入图片描述

1.初始化指针：

slow 和 fast 都初始化为链表的头节点 head。

2.循环条件：

循环的条件是 fast 和 fast->next 都不为空。这是因为如果链表中没有环，fast 或 fast->next 最终会指向 NULL，从而退出循环。

3.指针移动：

在循环中，slow 每次移动一步（slow = slow->next）。 fast 每次移动两步（fast = fast->next->next）。

4.检测环：

如果链表中存在环，fast 和 slow 最终会在环内相遇（即 slow == fast）。 如果链表中没有环，fast 或 fast->next 会先到达链表的末尾（NULL），循环结束。

5.返回结果：

如果在循环中检测到 slow == fast，说明链表中存在环，返回 true。 如果循环结束，说明链表中没有环，返回 false。

需要注意的地方

1.循环条件的顺序：

在循环条件 while(fast && fast->next) 中，fast 必须先于 fast->next 进行检查。如果先检查 fast->next，当 fast 为 NULL 时，访问 fast->next 会导致空指针解引用错误。

2.空链表的处理：

如果输入的链表为空（head == NULL），代码会直接返回 false，这是合理的，因为空链表显然不存在环。

3.链表中存在环的情况：

如果链表中存在环，fast 和 slow 会在环内相遇。此时，循环不会无限进行，因为快指针最终会追上慢指针。

 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(slow == fast)
        return true;
    }
    return false;
}

为什么快指针一定会追上慢指针？

假设链表中存在环，环的长度为 L，环的入口距离链表头部的距离为 D。

快指针和慢指针进入环的时刻：

慢指针每次移动一步，快指针每次移动两步。 当慢指针进入环时，快指针可能已经在环内，也可能尚未进入环。 但无论如何，快指针最终一定会进入环。

快指针追上慢指针的过程：

一旦快指针和慢指针都在环内，它们之间的相对速度为 2−1=1 步。 假设快指针进入环时，它与慢指针之间的距离为 k 步（k 是环长度 L 的某个倍数或部分）。 每次循环，快指针会比慢指针多走一步，因此它们之间的距离会逐渐减少。 最终，快指针和慢指针一定会相遇。

数学证明

1. 假设： 环的长度为 L。 慢指针进入环时，快指针与慢指针之间的距离为 k 步（k 是环长度 L 的某个倍数或部分）。
2. 每次循环： 慢指针移动 1 步。 快指针移动 2 步。 它们之间的距离减少 1 步。 因此，经过 k 次循环后，快指针和慢指针之间的距离会减少到 0，即它们会相遇。
3. 特殊情况 即使快指针和慢指针进入环的时刻不同，快指针最终也会追上慢指针。因为： 快指针在环内移动的速度是慢指针的两倍。 环的长度是有限的，快指针一定会在环内追上慢指针。

另外无论快指针速度是慢指针的几倍，快指针任然会追上慢指针；

二.环形链表进阶

环形链表进阶

在这里插入图片描述

在带环链表中，快慢指针相遇点和头节点到入环点的距离相等，下面是详细的证明过程：

1. 假设 设链表的头节点为head。 设环的入口节点为entry。 设快慢指针在环内相遇的节点为meeting。 设head到entry的距离为a。 从entry到meeting的距离为b。 从meeting再到entry的距离为c。 环的长度为r，即r = b + c。
2. 推导 快指针的速度是慢指针速度的 2 倍，当快慢指针相遇时，快指针走过的路程是慢指针的 2 倍。 慢指针走过的路程为s = a + b。 快指针走过的路程为2s = a + b + n * r（n为快指针在环中绕的圈数）。 将2s = a + b + n * r中的s用a + b替换，得到2(a + b)=a + b + n * r，进一步化简得到a + b = n * r，也就是a = n * r - b。 因为r = b + c，所以a = n * (b + c)-b=(n - 1) * r + c。
3. 结论 当n = 1时，a = c，即头节点到入环点的距离等于相遇点到入环点的距离。 当n > 1时，快指针在环中多绕了几圈，但仍然可以得出从head到entry的距离与从meeting到entry的距离在经过一定的环的整数倍调整后是相等的。

所以，在带环链表中，快慢指针相遇点和头节点到入环点的距离是相等的。这一结论可以用于在已知链表有环的情况下，寻找环的入口节点。 有了该结论，该题就会变的简单很多。

第一部分：检测环

1.初始化指针：

slow 和 fast 都初始化为链表的头节点 head。

2.循环条件：

循环的条件是 fast 和 fast->next 都不为空。这是因为如果链表中没有环，fast 或 fast->next 最终会指向 NULL，从而退出循环。

3.指针移动：

在循环中，slow 每次移动一步（slow = slow->next）。 fast 每次移动两步（fast = fast->next->next）。

4.检测环：

如果链表中存在环，fast 和 slow 最终会在环内相遇（即 slow == fast）。 如果链表中没有环，fast 或 fast->next 会先到达链表的末尾（NULL），循环结束。

第二部分：找到环的入口

1.相遇后重置指针：

当 slow 和 fast 相遇时，说明链表中存在环。 此时，将一个指针（如 pcur）重新指向链表的头节点 head，另一个指针（如 slow）保持在相遇点。

2.同步移动指针：

同时移动 pcur 和 slow，每次各移动一步。 当 pcur 和 slow 再次相遇时，它们相遇的节点就是环的入口。

3.返回环的入口：

返回 pcur（或 slow），即环的入口节点。

4.如果没有环：

如果循环结束时没有检测到环（即 fast 或 fast->next 为 NULL），返回 NULL。

 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(slow == fast)
        {
            ListNode* pcur = head;
            while(pcur != slow)
            {
                pcur = pcur->next;
                slow = slow->next;
            }
            return pcur;
        }
    }
    return NULL;
}