103. 带环链表 II

描述

给定一个链表，如果链表中存在环，则返回到链表中环的起始节点，如果没有环，返回null。

样例

给出 -21->10->4->5, tail connects to node index 1，返回10

挑战

不使用额外的空间

思路

本题更像一道数学题，判断是否有环用典型的快慢指针方法就可以解决，此处主要说怎么找到环的入口，设环的长度为 r，快指针的速度是慢指针的 2 倍，两个指针在第k步(可能已经绕环若干圈)相遇时，2k - k = nr 即 k = nr，设链表起始点到环的入口点(包括环的入口点)的距离是 s ，从环的起始点开始(不包含起始点)到相遇点的距离是 m (注意此处的 m 可能是包含若干个整圈距离再加上一个不足圈的环入口点到相遇点的距离) ，m + s = k 即 s = k - m => s = nr - m，那我们可以得出结论从快慢指针的相遇点往前出发走 s 步正好是环入口的上一个结点

代码

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 空结点或者不带环的单独结点 return null
        if (head == null || head.next == null) {
            return null;
        }

        ListNode fast, slow;
        fast = head.next;
        slow = head;
        // 先判断是否存在环
        while (fast != slow) {
            if (fast == null || fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        } 
        
        // slow 和 head 正好差一个结点，当 head 是环入口时，slow 是环入口的上一个结点
        while (head != slow.next) {
            head = head.next;
            slow = slow.next;
        }
        // 也可写 return slow.next;
        return head;
    }
}