Floyd 判圈法·

Floyd 判圈法

利用快慢指针，快指针步进速度为慢指针的两倍，若是链表中存在环，则两个指针一定会相遇，且快指针路程比慢指针路程多圈长度的整数倍。

假设两个指针在 PP 点相遇，则有

  • 快指针：2t=l+λs+d2t = l + \lambda s + d
  • 慢指针：t=l+μs+dt = l + \mu s + d

t=(λ−μ)st = (\lambda - \mu)s

【LeetCode】141. 环形链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    static bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
 			return false;
        }
        ListNode *low = head;
        ListNode *fast = head->next;
        while (fast != nullptr) {
            if (fast == low) {
            	return true;
            }
            if (fast->next == nullptr) {
                return false;
            }
            fast = fast->next->next;
            low = low->next;
        }

        return false;
    }
};

在验证存在环的前提下，令快指针不动，慢指针向后遍历节点，再次和快指针相等时，慢指针的步数即为环的长度。

在验证存在环的前提下，令慢指针回到起点，两个指针以相同速度步进，再次相遇时相遇点即为环起点。

上文已证明 t=(λ−μ)st=(\lambda - \mu)s，则 (λ−μ)s=l+μs+d(\lambda-\mu)s = l + \mu s + d，进而得到 l+d=(λ−2μ)sl + d = (\lambda - 2\mu)s，即

s∣l+ds | l + d

所以当慢指针步进 ll 到达环起点时，快指针也从 PP 步进 ll，距离环起点 l+dl+d 为环长度的整数倍，则快指针也到达了环起点。

Brent 判圈法·

令快慢指针指向起始节点，慢指针保持不动，快指针走 2i2^i 步，快指针每走一步，判断快慢指针是否相遇，如果相遇则存在环，如果走了 2i2^i 步后没有相遇或走到头，则将慢指针的位置移到快指针处，走下一轮……

第 ii 轮存在环的条件是，环长度 ≤2i\leq 2^i；