Thursday, June 12, 2014

LeetCode Linked List Cycle II

1. Find the cycle
2. Move the slow to the head

2(a+b) = a+b + b+ c; so a = c;

public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //Finding the cycle
        //Slow and fast meet at Z point
        while(true) {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
           
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
       
    }

No comments:

Post a Comment