0142.环形链表 ii

题目链接https://leetcode.cn/problems/linked-list-cycle-ii/题目描述给定单链表 head若链表中存在环返回环的第一个进入节点环的入口若不存在环则返回 null。解题思路Floyd 判圈 数学定位入口第一阶段快慢指针相遇判断是否有环。slow 每次一步fast 每次两步相遇则说明有环。第二阶段定位入口。将其中一个指针移到头节点两个指针改为每次各走一步再次相遇点即为环入口。原理说明距离记法设从头到入口距离为 a入口到相遇点为 b环长为 c。相遇时 fast 走了 2(ab)slow 走了 ab且 fast 比 slow 多走了若干圈2(ab) (ab) k·c → ab k·c → a ≡ (-b) mod c。因此从相遇点再走 a 步回到入口从头走 a 步也到入口两者同步一步步走会在入口相遇。题解代码publicclassSolution{publicListNodedetectCycle(ListNodehead){if(headnull||head.nextnull)returnnull;ListNodeslowhead,fasthead;// 阶段一判圈并找到首次相遇点while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;if(slowfast){// 阶段二从头与相遇点同时出发步长为1入口处相遇ListNodep1head,p2slow;while(p1!p2){p1p1.next;p2p2.next;}returnp1;// 或 p2}}returnnull;}}复杂度分析时间复杂度O(n)判圈与定位入口均为线性。空间复杂度O(1)仅使用常数级指针。