Linked List Cycle II (LeetCode Linked List)

Question: 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?

Idea: As we know, the faster pointer will catch up the slower pointer if there is a cycle. The solution is an extension of this idea. Since the explanation needs a little math, let us first set the following notations to make it easier to be understood.

x: the length of the non-cycle part.
r: the length of the cyclic part.
a: the distance from the cycle entry to the point faster meets slower.
s: the distance the slower has traversed.
n: the number of runs the faster has traversed the whole cycle when faster meets slower.

When faster meets slower, the faster (slower) has traversed 2s (s), which can be represented as:
                          2s=x+nr+a
                            s=x+a
so we have          s= nr
and                      nr=x+a -> x=nr-a

As we know the slower is at position a when faster and slower meet, if the slower goes forward nr-a steps, the slower will reach the entry of the cycle. Since x=nr-a, if we let another pointer slower2 start from the head and run x steps with speed 1 step/run. It will meet the slower at the entry of the cycle.

Therefore the algorithm is like this:
1) Let faster and slower meet.
2) Start another pointer slower2 from head.
3) Let slower and slower2 both run 1step/time.
4) slower and slower2 must meet at the entry of the cycle. Return the entry pointer.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   public ListNode detectCycle(ListNode head) {  
     if(head==null||head.next==null)  
       return null;  
     ListNode faster=head;  
     ListNode slower=head;  
     while(faster!=null&&faster.next!=null)  
     {  
       faster=faster.next.next;  
       slower=slower.next;  
       if(slower==faster)  
       {  
         ListNode slower2=head;  
         while(slower!=slower2)  
         {  
           slower=slower.next;  
           slower2=slower2.next;  
         }  
         return slower;  
       }  
     }  
     return null;  
   }  
 }