Leetcode 142 Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

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

Solution 1: use fast/slow pointers.

 public class Solution {  
   public ListNode detectCycle(ListNode head) {  
     ListNode fast=head, slow=head;  
     while (fast!=null && fast.next!=null) {  
       fast=fast.next.next;  
       slow=slow.next;  
       if (fast==slow) break;  
     }  
     if (fast==null || fast.next==null) return null;  
     ListNode p=head;  
     while (p!=slow) {  
       slow=slow.next;  
       p=p.next;  
     }  
     return p;  
   }  
 }