1. Find the cycle
2. Move the slow to the head
2(a+b) = a+b + b+ c; so a = c;
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
//Finding the cycle
//Slow and fast meet at Z point
while(true) {
if (fast == null || fast.next == null) {
return null;
}
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
No comments:
Post a Comment