找到链表中的环

一个链表中形成环的一个原因：

HashMap链表成环的原因和解决方案

在多线程的时候进行链表的操作，就很有可能产生环的问题。

可以参考下面的文章代码的思路。就是使用 快慢指针的方式进行遍历。

在慢指针遍历完一半时，快指针遍历一圈，保持对应的步长一直执行下去，则一定会在入口点重叠。

环形链表

原文链接：快慢指针解决环形链表

双指针的做法，快慢指针的经典题目

1. 判断一个链表是否有环

设置一快一慢两指针，快指针的步长为2，慢指针的步长为1。

如果存在环形链表，那么一定会存在相等的时刻。

public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

2.判断一个链表是否有环，如果有环，请找出这个入环节点，若没有返回null。

整体思路依旧采用快慢指针，至于如何找出这个入环节点，可以通过数学公式推导出规律。

推导如下：
X为起点，Y为快慢指针相遇的节点

由此可以看到，如果设置两个节点，一个从起点出发的节点A，一个从快慢指针相交的节点出发的节点B，保持同样的步长，二者一定会在入环节点处相遇。

public ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            ListNode pre = head;
            while (pre != slow) {
                slow = slow.next;
                pre = pre.next;
            }
            return slow;
        }
    }
    return null;
}