141. Linked List Cycle Leetcode Java

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Solution:

Floyd's cycle detection algorithm. Assume there is a cycle, and the cycle start at ath point. And the cycle length is c. We set two pointers one is tortoise and the other one is hare as two times faster than tortoise. And if there is a cycle, they will meet eventually at some point in the cycle. Assume this point is b steps away from ath point. So a+mc+b=2(a+nc+b). where m and n are the number of cycles that hare and tortoise traveled respectively. a+b =(m-2n)c. There must exist b to satisfy the equation. And so if they can meed at some point, there must be a cycle. The contraposition of this argument is simple to understand: If there is no cycle=> they can't meet. 

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