Given a linked list, return the node where the cycle begins. If there is no cycle, return null
.
Follow up:
Can you solve it without using extra space?
因为fast的速度是slow的两倍,所以fast走的距离是slow的两倍,有 2(a+b) = a+b+c+b,可以得到a=c(这个结论很重要!)。
我们已经得到了结论a=c,那么让两个指针分别从X和Z开始走,每次走一步,那么正好会在Y相遇!也就是环的第一个节点。
/** * 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 fast=head; ListNode slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; if(fast==slow) break; } if(fast==null||fast.next==null) return null; fast=head; while(fast!=slow){ fast=fast.next; slow=slow.next; } return fast; } }