Thursday, June 12, 2014

LeetCode: Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?

Solution:

We first detect if a cycle exists, as Linked List Cycle I. Then we keep a pointer in the same position and obtain the length of the loop. With that we just have to keep the fast pointer this amount of positions in advance and they will always cross where the cycle starts.

/**
 * 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) {
        int states = 0;
        if (head == null || head.next == null)
            return null;
        ListNode slowPointer = head;
        ListNode fastPointer = head.next;
        while(fastPointer!=null && fastPointer.next != null && fastPointer!=slowPointer)
        {
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
        }
        if (fastPointer != slowPointer)
            return null;
        int counter = 1;
        fastPointer = fastPointer.next;
        while(fastPointer!=slowPointer)
        {
            fastPointer = fastPointer.next;
            counter++;
        }
        fastPointer = head;
        for (int i=0; i< counter; i++)
            fastPointer = fastPointer.next;
        slowPointer = head;
        while(fastPointer!=slowPointer)
        {
            fastPointer = fastPointer.next;
            slowPointer = slowPointer.next;
        }
        return fastPointer;
    }
}

No comments :

Post a Comment