142. Linked List Cycle II Leetcode Java

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?

Solution:

Following the previous problem, we have to find the starting point.

According to the previous analysis. We know that, if there is a cycle, these two pointers will meet at some point in the cycle and this point will satisfy the equation: a+b =(m-2n)c. As we know c is the cycle length, so if we travel a steps from b, we will reach the starting point of the cycle ath position. In addition if we travel a steps from start point of list, we will reach the starting point of the cycle as well. The algorithm is based on this observation. Once we find the meeting point, we set one of the pointer back to starting point of the list and let those two points both walk one step each time till they meet again. The meeting point will be the starting point of the cycle.

 public ListNode detectCycle(ListNode head) {  
    if(head==null || head.next==null) return null;  
    ListNode walker=head;  
    ListNode runner=head.next;  
    while(runner!=null && runner.next!=null && walker!=runner){  
      walker=walker.next;  
      runner=runner.next.next;  
    }  
    if(walker!=runner) return null;  
    runner=runner.next;  
    walker=head;  
    while(walker!=runner){  
      walker=walker.next;  
      runner=runner.next;  
    }  
    return walker;  
   }