环形链表 II | LeetCode 142
内容提要
LeetCode 142题要求找出环形链表的入环第一个节点，无环则返回null。解法基于快慢指针：两指针相遇后，将其中一个重新指向头节点，然后两指针同速前进，再次相遇处即为入环起点。时间复杂度O(N)，空间复杂度O(1)。
延伸解读
为什么相遇后重指头节点能定位入环点
文章用步数关系解释：设慢指针走了k步，快指针走了2k步，多出的k步是环长的整数倍。若相遇点距环起点m步，则头节点到环起点为k-m步，而相遇点继续走k-m步也到环起点。因此将任一指针重指头节点后同速前进，再次相遇处即入环起点。
复杂度分析的实际含义
文章指出，判断相遇阶段慢指针走过距离不超过链表总长，寻找入环点阶段也不超过总长，故总时间为O(N)+O(N)=O(N)。空间上只用了快慢指针等常数变量，因此为O(1)。这意味着该解法无需额外哈希表记录节点，适合对空间有要求的场景。
题目约束与实现注意点
题目明确不允许修改链表，且pos仅用于评测系统标识环的位置，不作为参数传入。节点数范围在[0, 10^4]，空链表应返回null。实现时需先按141题思路判断是否有环，无环直接返回null；有环后再执行重指头节点和同速前进步骤。
Q&A
LeetCode 142 题要求返回什么？
给定一个链表的头节点 head，返回链表开始入环的第一个节点；如果链表无环，则返回 null。
如何用快慢指针找到环形链表的入环起点？
先用快慢指针判断是否有环。当两指针相遇时，将其中一个指针重新指向头节点 head，然后两个指针以相同速度前进，再次相遇的节点就是入环的第一个节点。
为什么快慢指针相遇后，重新指向头节点再同速前进就能找到环起点？
假设慢指针走了 k 步，快指针走了 2k 步，则快指针比慢指针多走 k 步，即环长度的整数倍。设相遇点距环起点距离为 m，则环起点距头节点距离为 k-m。从相遇点继续前进 k-m 步也恰好到达环起点，因此将任一指针指向 head 后同速前进，k-m 步后必在环起点相遇。
这个算法的时间复杂度和空间复杂度是多少？
时间复杂度为 O(N)，其中 N 为链表中节点的数目；空间复杂度为 O(1)。
题目中的 pos 参数是什么意思？
pos 是评测系统内部使用的整数，表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则链表中没有环。注意 pos 不作为参数传递给函数，仅用于标识链表的实际情况。
解决这个问题时可以修改链表吗？
不可以，题目明确要求不允许修改链表。
