每日算法题 19---142.环形链表Ⅱ

引言

在这个系列里面也讲过一道环形链表题，那道题是判断一个链表是否是环形链表，而这道题是找出环形链表的入口

题目

142.环形链表Ⅱ

要求

给定一个链表的头节点head，返回链表开始入环的第一个节点。如果链表无环，则返回null。如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。

示例

思路

在判断是否为环形链表时用到了快慢指针的原理，这道题依旧使用快慢指针先来判断是否为环形链表，判断是环形链表之后就来找入口，找入口的原理用到了数学知识：

假设链表有a+b个节点，链表头部到链表入口有 a 个节点，链表环有 b 个节点，设快指针走了 f 步，慢指针走了 s 步，快指针走的是慢指针的两倍（快慢指针的速度比）：f=2s；快指针比慢指针多走了 n 个环的长度（相遇的地方一定是链表环里的某个节点，因此多走了n个环的长度）：f=s+nb；将这两个式子整合得到s=nb，这意味着从开始到相遇，快慢指针分别走了2n、n个链表环

上述相遇过程理解清楚后，我们就来构造第二次相遇，使相遇的地点刚好是链表环的入口：令fast指针重新指向链表的头节点，此时 f=0，s=nb，快慢指针现在同时向前走一步，当fast指针走了 a 步后，slow指针走了 a+nb步，此时两指针相遇，同时站在了链表环的入口处（为什么说一定是入口呢？因为走 a+nb 步 ，即先走 a 步到入口节点，之后每绕 1 圈环（ b 步）都会再次到入口节点）

代码

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast=head; ListNode slow=head; while(true){ if(fast==null || fast.next==null){ return null; } fast=fast.next.next; slow=slow.next; if(fast==slow) break; } fast=head; while(slow!=fast){ slow=slow.next; fast=fast.next; } return fast; } }