Finding a loop in LinkedList.

To check whether a LinkedList has a loop or not is pretty straightforward. But, it becomes trickier when it comes to finding the start of the loop of a LinkedList.

Let's first address, how can we tell whether a linked list has a loop or not?

Simple, use tortoise and hare approach. Or you can think of a slow car, fast car. Slow car is moving 1 step at a time while the fast car is moving 2 steps at a time.

If our LinkedList has a straight path, means it does not have any loop, our fast car will have moved to the end without any problem. But if it does have a loop eventually slow car and a fast car will meet at some point. Think of a race track. Any two-car moving at different speeds will catch one another eventually. That means we do have a loop in the LinkedList.

Here is a simple java code for cycle detection:

https://leetcode.com/problems/linked-list-cycle/

public boolean hasCycle(ListNode head) {
    if(head==null || head.next==null){
        return false;
    }
    ListNode slow = head;
    ListNode fast = head;
    while(fast!=null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow==fast){
            return true;
        }
    }
    return false;
}
Pretty simple, right? Beautiful code.

Up till this point everything looks nice and simple. What if we are asked to find the start node of the loop?
For example:

LinkedList

Slow car needs to take 3 steps to land at the start node of the loop. In that same amount of time fast car would've moved 6 steps. What does that mean? That means by the time slow car is at the start of the loop our fast car will have moved 3 steps inside the loop. Now, what if our loop require less than 3 steps to complete 1 circle? In that case, we say our fast car completed (number of steps slow car takes to reach start of the loop,K)3 mod (loop_size,L)8 steps which is 3 (F), in this case.

Now, where will fast and slow car will collide?

When slow car is at the start node of the loop, our fast car is already 3 (F) steps ahead of slow car. We can also say our fast car is [L - F ] = 8-3 = 5(B) steps behind slow car(Since we are in a loop).

LinkedList

LinkedList

Just to make everything more nicer. After all this we will have something like this.

K mod L = F where K = 3, L = 8, F = 3
L - F = B where L = 8, F = 3, B = 5

Now, to collide with slow car how many steps fast car needs to make?

To understand that, let's think of it this way. A race track has 8 units of length. It will take the slow car 8 unit of time to complete one circle. In the same period of time, fast car would've completed 2 circles. So, if they start from the same position, a slow car and a fast car will meet again after 8 units of time. What if they start from a different position? What if the fast car starts 5(B) steps behind the slow car? They will meet after B unit of time.

LinkedList

In that time slow car would've progressed B steps and fast car would've progressed 2B steps. And since fast car was already F steps inside the loop we will see fast car is at (F+2B) mod L  = B steps from start node of the loop. [ (3 + (2x5)) mod 8 = 5].

LinkedList

Now, what is B? B is L-F. That means from B if we take F steps we will reach the starting node of the loop. But, we don't know what is the value of F is, but we do know F = K mod L, which is essentially the same as saying K = M x L + F (Here M can be any arbitrary value). So, we can also say, if we take K steps from the head of the list and from B we will find the starting node of the loop.

LinkedList

Using these intuition let's come up with the solution:

First, we need to find the cycle, where the fast and slow pointer will meet. This will be at K + B steps from the head into the loop. Once both our pointer arrive at the collision point, we know we will find the start of the loop if we can move K more steps. We don't know the K, but we do know if we go from head to start of the loop we will have traversed K steps. At the same time from inside the loop, from B, if we reach the start of the loop we will have traversed K steps. That means we don't need to know the K. We only need to take some more steps until 2 cars meet each other at the start of the loop.Just place slow car at the head LinkedList and fast car at the collision point and start moving one step at a time. Whenever fast and slow car meets is our start node of the loop.

Below code summarises everything discussed above:

https://leetcode.com/problems/linked-list-cycle-ii/

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