LeetCode 链表判断是否有环

链表

描述：Given a linked list, return the node where the cycle begins. If there is no cycle, return null

给定一个链表，返回开始出现环的节点，如果没有则返回空

首先判断链表是否有环可以使用快慢指针，即另一个快指针每次走两步，慢指针每次走一步，当两个指针相遇的时候即存在环。但是这里需要返回存在的环的开始节点。此时有两种情况

• 链表头尾相连，这个很简单最后得到的就是出现环的节点
• 链表的尾与链表中间的节点出现环

当链表尾与中间点出现环，我们需要计算最后两个指针相遇的位置与交叉点的距离，参考leetcode上的实现。

我们假设从起点到相遇的点距离为k，环的长度为r，则2k-k=nr,假设交叉点距离相遇点距离为m，起点距离交叉点距离为s；则s=k-m =nr-m=(n-1)r+(r-m)
假设n等于1，则s=r-m,即我们可以从起点和相遇的点到交叉点距离一样。
下面是Java代码实现

public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        boolean isCycle = false;
        int i = 0;
        while (fast != null) {
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                //
                isCycle = true;
                break;
            }
        }
        slow = head;
        if (isCycle) {
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
        } else {
            return null;// 没有环
        }
        return fast;
    }