题目内容

给定一个链表的头节点 head，请返回该链表开始进入环形的第一个节点；如果链表中不存在环，则返回 None。

如果从某个节点出发，沿着 next 指针不断移动，可以再次到达该节点，就称链表中存在环。

约束条件

• 链表节点数量 $n$ 满足 $0 \le n \le 10^4$。
• 节点值 $Node.val$ 满足 $-10^5 \le Node.val \le 10^5$。
• pos 满足 $-1 \le pos < n$，且当 $n = 0$ 时，pos 必为 -1。

输入描述

输入包含一个参数：

• head：链表的头节点。链表节点包含 val 和 next 两个字段；如果链表为空，则 head 为 None。

整数 pos 表示链表尾节点的 next 所指向的节点下标（下标从 0 开始）。若 pos 为 -1，则表示链表没有环。pos 仅用于说明链表的实际结构，不会作为参数传入。

输出描述

返回链表中开始入环的第一个节点。如果链表中不存在环，则返回 None。

样例1

输入

0

输出

-1

说明

输入链表为空。没有任何节点，因此也不存在环，返回 None。

样例2

输入

1
100
0

输出

0

说明

样例3

输入

5
1 2 3 4 5
-1

输出

-1

说明

样例4

输入

6
1 2 3 4 5 6
2

输出

2

说明