LeetCode刷题记录：（2）环形链表

LeetCode传送阵

题目描述：

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。
如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
不允许修改 链表。
.
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
.

时间复杂度: O(n)
空间复杂度: O(1)

上代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next; // slow走一步
            fast = fast.next.next; // fast走两步，相对slow走一步
            // 如果slow可以追上fast则一定有环，反之亦然
            if(slow == fast){
                // 寻找入环节点
                ListNode idx1 = slow; // idx1 标记相遇节点
                ListNode idx2 = head; // idx2从头滑动，当与滑动的idx1 遇见时即为入环节点
                while(idx1!=idx2){
                    idx1 = idx1.next;
                    idx2 = idx2.next;
                }
                return idx1;
            }
        }
        return null;
    }
}

重点说明：

在通过快慢指针确定有环后，为什么 idx1 与 idx2 相遇的节点就是入环节点？
.