Problem

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If posis -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Solution

判断链表是否有环

穷举比较法

（1）遍历链表，记录已访问的节点。（2）将当前节点与之前以及访问过的节点比较，若有相同节点则有环。否则，不存在环。

这种穷举比较思想简单，但是效率过于低下，尤其是当链表节点数目较多，在进行比较时花费大量时间，时间复杂度大致在 $O(n^2)$。这种方法自然不是出题人的理想答案。如果笔试面试中使用这种方法，估计就要跪了，忘了这种方法吧。

哈希缓存法

既然在穷举遍历时，元素比较过程花费大量时间，那么有什么办法可以提高比较速度呢？

（1）首先创建一个以节点 ID 为键的 HashSe t集合，用来存储曾经遍历过的节点。（2）从头节点开始，依次遍历单链表的每一个节点。（3）每遍历到一个新节点，就用新节点和 HashSet 集合当中存储的节点作比较，如果发现 HashSet 当中存在相同节点 ID，则说明链表有环，如果 HashSet 当中不存在相同的节点 ID，就把这个新节点 ID 存入 HashSet ，之后进入下一节点，继续重复刚才的操作。

假设从链表头节点到入环点的距离是 a ，链表的环长是 r 。而每一次 HashSet 查找元素的时间复杂度是 O(1), 所以总体的时间复杂度是 1 * ( a + r ) = a + r，可以简单理解为 O(n) 。而算法的空间复杂度还是 a + r - 1，可以简单地理解成 O(n) 。

实现

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null)
            return false;

        Set<ListNode> set = new HashSet();
        while (true) {
            ListNode node = head.next;
            if (node == null) {
                return false;
            }

            if (set.contains(node))
                return true;
            else {
                set.add(node);
                head = node;
            }
        }
    }
}

快慢指针法

（1）定义两个指针分别为 slow，fast，并且将指针均指向链表头节点。（2）规定，slow 指针每次前进 1 个节点，fast 指针每次前进两个节点。（3）当 slow 与 fast 相等，且二者均不为空，则链表存在环。

无环过程

通过图解过程可以看出，若表中不存在环形，fast 与 slow 指针只能在链表末尾相遇。

有环过程

图解过程可以看出，若链表中存在环，则快慢指针必然能在环中相遇。这就好比在环形跑道中进行龟兔赛跑。由于兔子速度大于乌龟速度，则必然会出现兔子与乌龟再次相遇情况。因此，当出现快慢指针相等时，且二者不为NULL，则表明链表存在环。

实现

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

class Solution {
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null)
            return false;

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast)
                return true;
        }

        return false;
    }
}

public class Test {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(3);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(0);
        ListNode n4 = new ListNode(-4);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;

        Solution.hasCycle(n1);
    }
}

定位环入口

slow 指针每次前进一个节点，故 slow 与 fast 相遇时，slow 还没有遍历完整个链表。设 slow 走过节点数为 s，fast 走过节点数为 2s。设环入口点距离头节点为 a，slow 与 fast 首次相遇点距离入口点为 b，环的长度为 r。则有： s = a + b; 2s = n * r + a + b; n 代表fast指针已经在环中循环的圈数。则推出： s = n * r; 意味着slow指针走过的长度为环的长度整数倍。

若链表头节点到环的末尾节点度为 L，slow 与 fast 的相遇节点距离环入口节点为 X。则有： a+X = s = n * r = (n - 1) * r + (L - a); a = (n - 1) * r + (L - a - X); 上述等式可以看出：从 slow 与 fast 相遇点出发一个指针 p1，请进 (L - a - X) 步，则此指针到达入口节点。同时指针 p2 从头结点出发，前进 a 步。当 p1 与 p2 相遇时，此时 p1 与 p2 均指向入口节点。

例如图3.1所示链表： slow 走过节点 s = 6； fast 走过节点 2s = 12；环入口节点据流头节点 a = 3；相遇点距离头节点 X = 3； L = 8； r = 6；可以得出 a = (n - 1) * r + (L - a - X)结果成立。

图解过程

计算环长度

令 solw 与 fast 指针从相遇节点出发，按照之前的前进规则，当 slow 与fast 再次相遇时，slow 走过的长度正好为环的长度。

图解过程

Reference

几道和「链表」有关的面试题 - https://cxyxiaowu.com/articles/2019/04/04/1554346134716.html

[刷题] LinkedList - Leetcode - 141 Linked List Cycle