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.


public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) 
            return null;
        ListNode slow = head, fast = head; 
        while (true) {
            if (slow.next != null) {
                slow = slow.next; 
            } else {
                return null; 
            }
            if (fast.next != null && fast.next.next != null) {
                fast = fast.next.next; 
            } else {
                return null; 
            }
            if (slow == fast) {
                //find the loop start; 
                //1.start fast from the begining 
                //2.let the slow stay in the circle 
                fast = head; 
                while (slow!=fast) {
                    slow = slow.next; 
                    fast = fast.next; 
                }
                return slow ;
            }
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s