假设非环部分的长度是 x, 从环起点到相遇点的长度是 y. 环的长度是 c.
现在走的慢的那个指针走过的长度肯定是 x+n1*c+y, 走的快的那个指针的速度是走的慢的那个指针速度的两倍. 这意味着走的快的那个指针走的长度是 2(x+n1*c+y).
还有一个约束就是走的快的那个指针比走的慢的那个指针多走的路程一定是环长度的整数倍. 根据上面那个式子可以知道 2(x+n1*c+y)-x+n1*c+y=x+n1*c+y=n2*c.
所以有 x+y=(n2-n1)*c, 这意味着什么? 我们解读下这个数学公式: 非环部分的长度 + 环起点到相遇点之间的长度就是环的整数倍. 这在数据结构上的意义是什么? 现在我们知道两个指针都在离环起点距离是 y 的那个相遇点, 而现在 x+y 是环长度的整数倍, 这意味着他们如果从相遇点再走 x 就到了起点.
那怎么才能再走 x 步呢? 答: 让一个指针从头部开始走, 另一个指针从相遇点走, 等这两个指针相遇那就走了 x 步此时就是环的起点.
- /**
- * 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) {
- if(head == null){
- return null;
- }
- ListNode f = head;
- ListNode s = head;
- while(f != null && f.next != null){
- f = f.next.next;
- s = s.next;
- if(f == s){
- f = head;
- while(f != s){
- f = f.next;
- s = s.next;
- }
- return f;
- }
- }
- return null;
- }
- }
来源: http://www.bubuko.com/infodetail-3302506.html