图解

思路

1. 快慢两个指针, 初始化指向头结点
2. 快指针向前走两步, 慢指针向前走一步.
3. 如果快指针遇到了空结点, 结束返回
4. 否则, 快慢指针必将相遇.
5. 令环的长度为L, 头结点为A, 环起点为B, 相遇点为C.
6. 相遇时假设慢指针走了AB+KL+BC, 那么快指针走了2(AB+KL+BC)
7. 因为二者会相遇, 所以2(AB+KL+BC)-(AB+KL+BC)=L
8. 所以有 AB+KL+BC=L, 等价于AB+BC=L, 另有CB+BC=L
9. 所以AB = CB, 即从头结点A到环入口B的距离, 与从相遇点到环入口B的距离相同. 即找到相遇的点后, 用两个指针分别从相遇点和头结点出发, 二者相遇时就找到了环的入口.

代码

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