题目描述

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

思路

先说结论：

1. 快慢指针，让两个结点相遇；
2. 相遇后，让其中一个结点回到链表头结点，另一个结点处于相遇位置；
3. 两个指针都以速度1同时向后遍历，他们相遇时的结点就是入环点；

分析：
见小灰算法之旅p159.

public class Solution_142 {
    public ListNode detectCycle(ListNode head) {
        // 特殊判断
        if (head == null) {
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        // 判断有没有环，如果无环，那么会结束循环
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 如果快慢指针相遇，说明有环
            if (fast == slow) {
                break;
            }
        }
        // 无环的处理
        if (fast == null || fast.next == null) {
            return null;
        }
        // 有环的时候，让某个指针回到head
        fast = head;
        // fast和slow一起往后走，每次只走一步。
        // 再次相遇点就是环的起点
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}