Leetcode 141.环形链表-原题链接

题目描述

给定一个链表的头节点 $head$，判断链表中是否存在环。

如果链表中存在某个节点，可以通过连续跟踪 $next$ 指针再次到达该节点，则说明链表中存在环。

为了表示给定链表中的环，使用整数 $pos$ 表示链表尾节点连接到链表中的位置，索引从$0$开始。

如果 $pos = -1$，则表示链表中没有环。

注意：$pos$ 不作为输入链表检测函数的参数进行传递，仅用于表示链表的实际结构。

如果链表中存在环，则输出 $true$；否则输出 $false$。

输入描述

第一行输入一个整数 $n$，表示链表中节点的数量。

第二行输入 $n$ 个整数，表示链表中每个节点的值 $Node.val$。

第三行输入一个整数 $pos$，表示链表尾节点连接到链表中的位置。

其中：

• 当 $pos = -1$ 时，表示链表中没有环；
• 当 $0 \le pos < n$ 时，表示链表尾节点连接到下标为 $pos$ 的节点。

输出描述

输出一个布尔值。

如果链表中存在环，输出 $true$。

否则，输出 $false$。

样例1

输入

4
3 2 0 -4
1

输出

true

样例解释

链表中存在一个环，其尾部连接到第二个节点，即下标为 $1$ 的节点。

样例2

输入

2
1 2
0

输出

true

样例解释

链表中存在一个环，其尾部连接到第一个节点，即下标为 $0$ 的节点。

样例3

输入

1
1
-1

输出

false

样例解释

链表中不存在环。

数据范围

• $0 \le n \le 10^4$
• $-10^5 \le Node.val \le 10^5$
• $pos = -1$ 或 $pos$ 是链表中的一个有效下标

进阶要求

你能使用 $O(1)$ 的额外内存解决此问题吗？