Linked List Cycle II详解程序员

Note: Do not modify the linked list.

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

代码实现：

/** 
 * Definition for singly-linked list. 
 * class ListNode { 
 *     int val; 
 *     ListNode next; 
 *     ListNode(int x) { 
 *         val = x; 
 *         next = null; 
 *     } 
 * } 
 */ 
public class Solution { 
    public ListNode detectCycle(ListNode head) { 
        if(head==null) return null; 
        ListNode fast=head; 
        ListNode slow=head; 
        do{ 
            if(fast!=null) fast=fast.next; 
            if(fast!=null){ 
            	fast=fast.next; 
            }else{ 
                return null; 
            } 
            slow=slow.next; 
        }while(fast != slow);    
         
        slow=head; 
        while(fast!=slow){ 
            fast=fast.next; 
            slow=slow.next; 
        } 
 
        return slow; 
    } 
}