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:

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).

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 = 3L - 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.

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].

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**.

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;
}
```