0142.环形链表 ii

题目链接

https://leetcode.cn/problems/linked-list-cycle-ii/

题目描述

给定单链表 head，若链表中存在环，返回环的第一个进入节点（环的入口）；若不存在环则返回 null。

解题思路

• Floyd 判圈 + 数学定位入口
  • 第一阶段：快慢指针相遇判断是否有环。slow 每次一步，fast 每次两步；相遇则说明有环。
  • 第二阶段：定位入口。将其中一个指针移到头节点，两个指针改为每次各走一步；再次相遇点即为环入口。
• 原理说明（距离记法）：
  • 设从头到入口距离为 a，入口到相遇点为 b，环长为 c。
  • 相遇时 fast 走了 2(a+b)，slow 走了 a+b，且 fast 比 slow 多走了若干圈：2(a+b) = (a+b) + k·c → a+b = k·c → a ≡ (-b) mod c。
  • 因此从相遇点再走 a 步回到入口；从头走 a 步也到入口，两者同步一步步走会在入口相遇。

题解代码

publicclassSolution{publicListNodedetectCycle(ListNodehead){if(head==null||head.next==null)returnnull;ListNodeslow=head,fast=head;// 阶段一：判圈并找到首次相遇点while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(slow==fast){// 阶段二：从头与相遇点同时出发，步长为1，入口处相遇ListNodep1=head,p2=slow;while(p1!=p2){p1=p1.next;p2=p2.next;}returnp1;// 或 p2}}returnnull;}}

复杂度分析

• 时间复杂度：O(n)，判圈与定位入口均为线性。
• 空间复杂度：O(1)，仅使用常数级指针。