103. Linked List Cycle II

Leave a comment

June 14, 2016 by oneOokay

use fast pointer and slow pointer.

after they meet, move slow pointer to the head, move one step by one step.

NOTE:

if you initialize your  fast pointer = slow pointer, then when fast pointer == slow pointer, return. that’s where the cycle begins.

if you initialize your fast pointer  = slow.next, then when slow.next == fast pointer return.

just remember the solution. that’s it

SOLUTION:

    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next==null) {
            return null;
        }

        ListNode fast, slow;
        fast = head.next;
        slow = head;
        while (fast != slow) {
            if(fast==null || fast.next==null)
                return null;
            fast = fast.next.next;
            slow = slow.next;
        } 
        
        while (head != slow.next) { 
            head = head.next;
            slow = slow.next;
        }
        return head;
    }

 

MINE:

public ListNode detectCycle(ListNode head) {
// write your code here
if(head == null || head.next == null)
return null;

ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow)
{
slow = head;
while(fast != slow){
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
return null;
}

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

%d bloggers like this: