100 Days of Code #Day11

New Day, New problem. Today we are going to solve the classic problem of finding a loop in the linked list. But we are adding a touch to that we have to return the starting index of the loop.

Write a function that takes in the head of a Singly Linked List that contains a loop (in other words, the list’s tail node points to some node in the list instead of None / null). The function should return the node (the actual node — not just its value) from which the loop originates in constant space.

head = 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 // the head node with value 0
                           ^         v
                           9 <- 8 <- 7

Okay, seeing the problem we can solve it by two approaches one uses a constant space and O(n) time which is optimal and another uses a O(n) space and O(n) time.

Approach 1:

This is somewhat a naive approach. We can build a set of Linked List Nodes, and insert the nodes one by one into set while iterating through the linked list. If there is a duplicate found there is a loop and the duplicate Linked List Node is the start of the index.

This is based on the fact that each memory node will be different and no two linked list nodes even though having the same value will have different addresses pointed to them so this approach will work.

Yes this approach will work but We are using O(n) space. If we process millions of elements it will take million space additionally. This is not good. Can we do it differently.

Approach 2:

Two Pointer Approach. The widely used approach to solve the problem of find if there is an loop present in the linked list.

The approach is simple :

1. Initialize two nodes to the head.
2. Move the first node fast by moving two nodes at a time and the other node slow by moving one node at a time.
3. At one point the two nodes will meet and if so there is a loop in the linked list. If not there is no loop

But there is no guarantee that the pointers meet at the start of the loop. So now we have found there is a loop but we have to find the start of the loop. So I started analyzing the cases.

1->2->3->4->5->3( goes to 3)

so on first iteration first node moves to 3 and second node moves to 2, then the first node moves to 5 the second node moves to 3.Then it goes on to move to 4 also the second node moves to 4.

Now here they haven’t met at the start of the loop instead an element within the loop. Okay from here it will take 2 steps to reach the start of the loop 3. The irony is it will take same 2 steps to reach 3 from 1. Is this coincidence let’s have a look at another case.

1->2->3->4->5->6->3(goes to three)

On first iteration first node -> 3, second node -> 2. first node -> 5 secondnode ->3. firstNode -> 3, secondNode -> 4. first node -> 5, secondNode -> 5

Here too the distance to reach the start of the loop from 5 is 2 and distance to reach start of the loop from head is 2.

So assuming it fits for all the cases

#100DaysofCode #Day11