链表：环

0141. 环形链表 (opens new window)

题目

给定一个链表，判断链表中是否有环。

解析

本题是 0142. 环形链表 II 的简化版，只需判断快慢指针能否相遇即可。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

0142. 环形链表 II (opens new window)

题目

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

解析

我们使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。

根据上图可知，在第一次相遇时，fast 指针走过的节点数为：$x+y+n(y+z)$，slow 指针走过的节点数：$x+y$，由于 fast 走的距离是 slow 的两倍，因此有

$\begin{aligned} 2(x+y)&=x+y+n(y+z)\\ x+y&=n(y+z)\\ x&=n(y+z)-y\\ x&=(n-1)(y+z)+z \end{aligned}$

可以看到，$y+z$ 是环的长度，只需要定义两个指针，分别从相遇节点和头节点出发，那么一定会在环入口处相遇。

补充说明

1. 为什么在 slow 入环时，fast 可以在一圈内追上 slow，即第一次相遇时 slow 指针走过的节点数为 $x+y$ ？

   首先 slow 进环的时候，fast 一定是先进环了。假设此时 fast 在环入口处，slow 想要走完一圈的话，由于 fast 速度是 slow 的 2 倍，fast 一定走完了两圈并与 slow 在入口处相遇。

   由于在 slow 进环时 fast 可能在环中任意一处，即 slow 与 fast 的距离不超过环的长度，因此 fast 一定可以在一圈内追上 slow。

2. 为什么要设置 fast 指针速度是 slow 的 2 倍，而不是 3 倍？

   这样 fast 指针相对于 slow 指针是一次移动一个节点，可以保证两指针必定相遇，而不是跳过去。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};