链表是否有环

1. 哈希

最容易想到的方法是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。
具体地，我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

1. 快慢指针

具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

1. 翻转链表

对于环形链表来说，翻转后的头结点和翻转前的头结点是同一个节点。

public boolean hasCycle(ListNode head) {
    ListNode newHead = head;
    ListNode temp = null;
    while (head != null) {
        // 保存链表的下一节点
        ListNode next = head.next;
        // 将旧节点拼接到新节点头部
        head.next = temp;
        // 新链表指针指向链表头结点
        temp = head;
        // 定位到旧链表的下一个节点
        head = next;
    }
    if (temp != null && temp.next != null && temp == newHead) {
        return true;
    }
    return false;
}

求环的长度

当两个指针首次相遇，证明链表有环的时候，让两个指针从相遇点继续循环前进，并统计前进的循环次数，直到两个指针第2次相遇。此时，统计出来的前进次数就是环长。
因为指针 p1 每次走 1 步，指针 p2 每次走 2 步，两者的速度差是 1 步。当两个指针再次相遇时，p2 比 p1 多走了整整 1 圈。
因此，。

求入环点

上图是对有环链表所做的一个抽象示意图。假设从链表头节点到入环点的距离是 D ，从入环点到两个指针首次相遇点的距离是 S1，从首次相遇点回到入环点的距离是 S2。
那么，当两个指针首次相遇时，各自所走的距离是多少呢？
指针 p1 一次只走 1 步，所走的距离是。指针 p2 一次走 2 步，多走了 n (n ＞=1) 整圈，所走的距离是。
由于 p2 的速度是 p1 的 2 倍，所以所走距离也是 p1 的 2 倍，因此：

等式经过整理得出：
也就是说，从链表头结点到入环点的距离，等于从首次相遇点绕环 n -1 圈再回到入环点的距离。
这样一来，只要把其中一个指针放回到头节点位置，另一个指针保持在首次相遇点，两个指针都是每次向前走 1步。那么，它们最终相遇的节点，就是入环节点。