Leetcode 142.环形链表Ⅱ-原题链接

题目描述

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

如果链表中存在某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，输入数据中使用整数 pos 来表示链表尾部连接的索引（索引从 0 开始）。如果 pos 为 -1，则表示该链表中没有环。

注意：pos 不作为参数进行传递，仅用于描述链表的实际情况，输入数据仅提供链表的结构。

不允许修改链表。

输入描述

• 第一行输入一个整数 n（$0 \leq n \leq 10^4$），表示链表的节点数。
• 第二行输入 n 个整数，表示链表节点的值（按顺序存储）。
• 第三行输入一个整数 pos（$-1 \leq pos < n$），表示链表尾部连接的索引，-1 代表无环。

如果 n == 0，则链表为空，此时 pos 必定为 -1，且不输入第二行数据。

输出描述

• 如果链表有环，返回环的起始节点的索引（从 0 开始）。
• 如果链表无环，返回 "-1"。

样例1

输入

4
3 2 0 -4
1

输出

1

说明

链表中有一个环，其尾部连接到索引 1 的节点（值 2）。

样例2

输入

2
1 2
0

输出

0

说明

链表中有一个环，其尾部连接到索引 0 的节点（值 1）。

样例3

输入

1
1
-1

输出

-1

说明

链表中没有环。

提示

• 链表的节点值范围：$-10^5 \leq \text{Node.val} \leq 10^5$。
• pos 仅用于构造链表，实际链表中不包含 pos 信息。
• pos = -1 表示链表无环。