链表带环检测与入口定位：快慢指针法原理及实现

1.4 数学证明

1.4.1 为什么带环 slow 与 fast 必定能相遇？

假设 slow 进环时与 fast 的差距为 N，那么接下来就是追击问题，slow 每次走一步，fast 每次走两步。那么每走完一次 slow 的距离就会变成：N - 1，N - 2，N - 3…2,1,0，故必定会相遇。

1.4.2 fast 一定只能走 2 步吗？可以是 2 步甚至更多吗？

1.4.2.1 以 3 步为例

假设 slow 进环时与 fast 的差距为 N，那么接下来就是追击问题，slow 每次走一步，fast 每次走三步。会分成两种情况: • 当 N 是偶数时：N - 2，N - 4，N - 6…4，2，0 • 当 N 是奇数时：N - 2，N - 4，N - 6…3，1，-1

也就是当 N 是偶数时，必定会相遇，当 N 是奇数时最后距离为 -1，也就是会错过，如果假设圆环周长为 C，那么当 N 是奇数时且 fast 与 slow 错过后进入新一轮追击，距离变为 C-1，那么又会变成两个的情况： • 当 N = C -1 是偶数时 (C 为奇数)：N - 2，N - 4…4，2，0 • 当 N = C - 1 是奇数时 (C 为偶数）：N - 2，N - 4…3，1，-1 综上我们可以分析出要让 slow 和 fast 不相遇只有一种可能：C 为偶数且第一轮追击中 N 为奇数同时成立。 C 为偶数且第一轮追击中 N 为奇数能同时满足吗？ 那我们还是假设当 slow 进环时，slow 与 fast 相距 N: slow 走过的距离：L。 fast 走过的距离为：L + C * x(x:为绕环圈数) + C - N。 slow 与 fast 始终满足：fast = 2 * slow。 联立上面三个式子可得：2L = (x+ 1) * C - N ,我们分析可得该等式为：偶数 = （x + 1） 偶数 - 奇数不成立，故两个条件无法同时成立，故不会永远追不上，slow 和 fast 必定相遇。

1.4.3 结论

• 链表带环，使用快慢指针，无论 fast 走几步，都必定在环内与 slow 相遇。

二、环形链表（寻找相遇点）

2.1 题目

链接：环形链表（寻找相遇点）

2.2 算法原理

2.3 代码

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

2.4 数学证明

H 为链表的起始点，E 为环入口点，M 与判环时候相遇点 设：环的长度为 R，H 到 E 的距离为 L，E 到 M 的距离为 X 则：M 到 E 的距离为 R - X。在判环时，快慢指针相遇时所走的路径长度: fast: L + X + nR slow: L + X

注意： 当慢指针进入环时，快指针可能已经在环中绕了 n 圈了，n 至少为 1 因为：快指针先进环走到 M 的位置，最后又在 M 的位置与慢指针相遇 慢指针进环之后，快指针肯定会在慢指针走一圈之内追上慢指针。 因为：慢指针进环后，快慢指针之间的距离最多就是环的长度，而两个指针在移动时，每次它们之间的距离都缩减一步，因此在慢指针移动一圈之前快指针肯定是可以追上慢指针的。

极端情况下，假设 n = 1，此时：L=R−X 即：一个指针从链表起始位置运行，一个指针从相遇点位置绕环，每次都走一步，两个指针最终会在入口点的位置相遇

2.4.1 结论

• 让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。