LeetCode 141.环形链表

1 题目概述

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例1：

在遍历此链表时，指针会在 2 到 -4 的这段区域不断地循环遍历，因此链表中存在环

示例2：

在遍历此链表时，指针不会循环遍历链表，最终会停止，因此链表中不存在环

2 题目解法

在解决这道题目时所采用的方法是快慢指针法，在使用快慢指针时，保证慢指针每次走一步，快指针每次走两步，最终快慢指针相遇，就能说明链表中存在环。如果快指针为空或快指针的下个结点为空，则不存在环。

存在环：

不存在环：
偶数个结点时

奇数个结点时

代码如下

bool hasCycle(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)
            return true;
    }

    return false;
}

3 证明

为什么慢指针走一步，快指针走两步的话，有环时它们一定能相遇呢？如果慢指针走一步，快指针走三步，四步行不行呢？

首先来说说为什么慢指针走一步，快指针走两步的话，有环时它们一定能相遇
以下面的链表为例：

在 slow 指针逐渐逼近环时，fast 指针已经在环内游走了一段时间，最终 slow 指针进入环时，呈现出来的形式是这样的：

此时，fast 和 slow 的距离为 4
继续移动 slow 和 fast：

此时，fast 和 slow 的距离为 3
继续移动：

此时，fast 和 slow 的距离为 2
继续移动：

此时，fast 和 slow 的距离为 1
继续移动：

此时，fast 和 slow 的距离为 0
于是，我们可以发现，在快指针一次走两步，慢指针一次走一步的情况下，快慢指针之间的距离会逐渐缩小，每次缩小1，直到最后距离差为0

因此我们可以假设，在 slow 指针刚进环时，fast 和 slow 之间的距离为 N

在 fast 和 slow 逐渐移动的过程中，距离 N 会不断减 1，变成 N-1，N-2，N-3 … 1， 0
当距离为 0 时，fast 和 slow 即可相遇，因此在快指针一次走两步，慢指针一次走一步的情况下，两指针一定可以相遇

再来说说如果慢指针走一步，快指针走三步，四步能不能让它们相遇
在这里以慢指针走一步，快指针走三步为例：
仍然假设在 slow 指针刚进环时，fast 和 slow 之间的距离为 N

此时如果让快慢指针开始移动，那么快慢指针之间的距离差会逐渐减少 2
变成 N-2，N-4，N-6，N-8 …
如果 N 是偶数，则距离最终会变成 0
如果 N 是奇数，则距离最终会 变成 -1
距离是 0，表示 slow 和 fast 相遇

距离是 -1，表示 slow 和 fast 刚好错过，无法相遇

在这个情况下，需要再次遍历环，假设环的长度为 C，那么fast 与 slow 的距离就是 C-1

在遍历的过程中，C-1又会不断地减2
C-1 为偶数时，最终会变成 0，最终会相遇
C-1 为奇数时，最终会变成 -1，最终不会相遇
根据前面的结论，如果一直不相遇，那么 N 是奇数，C是偶数
真的是这样吗？
如果环内的结点较少，环外的结点较多，则在慢指针刚进环时，快指针很有可能已经走了很多圈
因此，我们可以假设链表的起始位置到环的第一个结点的距离为 L，快慢指针的距离为 N，环的长度为 C

此时，slow 走过的距离为 L，fast 走过的距离为 L + (x * C) + (C - N) (x为走过的环的个数)
又因为 fast 的速度为 slow 的三倍，则距离也为 slow 的三倍
因此可以得到等式 3L = L + (x * C) + (C - N)
化简可得 2L = (x + 1) * C - N
根据我们得到的结论，如果一直不相遇，那么 N 是奇数，C 是偶数，将这个条件代入式中，会发现并不成立，因为偶数 ≠ 偶数 - 奇数，在这样的情况下，N 和 C 的取值只有下面两种情况：
N 为奇数，C 为奇数
N 为偶数，C 为偶数
当 N 为奇数，C 为奇数时，C - 1为偶数，最终距离会为0，快慢指针第一次不会相遇，遍历第二次肯定会相遇
当 N 为偶数时，快慢指针一定会相遇
所以，slow 走一步，fast走三步，四步甚至更多时，仍然会相遇