I’m still unclear about the solution to the question. Why do we need to move the fast pointer by the length of the cycle? Any rationale behind it would be helpful!
Hi @Soo,
Yes, there is a logic let me explain it to you.
Suppose we have a list 1->2->3->4->5->6 and the next to 6 is 3 which is making a cycle.
The length of the cycle is 4 now. pointer1 is pointing at the head node having value 1 and pointer 2 should be incremented by 4 and now it will point to the node having value 5. Now let’s start incrementing both pointers, they will meet at the node having value 3 (at the start of the cycle).
Hi Ammar
Yes the example works and the logic works, but I am trying to understand the rationale behind it. maybe through some proof
Hi @Soo ,
So the general idea is
- when the fast and slow pointer meet at the same node,
- we can just initialize the slow pointer back to the head node,
- again starting to increment the fast and slow nodes by one position in a loop, until they meet at the starting of the cycle.
Now at step 1, it’s been observed that the distance from the meeting point and the head are always K places. So they always tell to increment a pointer p2 by K places and then start the search for equality.
By the above approach, we don’t even need to find the length of the linked list cycle, and becomes a more simple solution as below.
public ListNode findCycleStart(ListNode head) {
ListNode curr=head;
ListNode slow=curr, fast=curr;
while(fast!=null && fast.next!=null) {
slow=slow.next;
fast=fast.next.next;
if(slow==fast)
break;
}
if(fast==null || fast.next==null) return null;
slow=head;
while(slow!=fast) {
slow=slow.next;
fast=fast.next;
}
return slow;
}
2 Likes