解题思路

本题要求在 不修改链表 的前提下，找到链表入环的第一个节点（如果有环），否则返回 null。

可以使用 快慢指针（Floyd 判圈算法） 来解决这个问题：

解法：快慢指针（Floyd 判圈算法）

1. 第一阶段：判断链表是否有环
   • 设定 慢指针 slow 和 快指针 fast，都从 head 出发：

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

题目描述

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

如果链表中存在某个节点，可以通过连续跟踪 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 开始）。
• 如果链表无环，返回 "null"。

样例1

输入

4
3 2 0 -4
1

输出

1

说明

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

样例2

输入

2
1 2
0

输出

0

说明

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

样例3

输入

1
1
-1

输出

null

说明

链表中没有环。

提示

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