Detect Loop In Linked List – Interview Question

Detect Loop In Linked List – Interview Question

January 18, 2019 Uncategorized 0

To begin with you can draw a linked list on the whiteboard. A linked list has nodes in it which are connected to each other. Each node has two components: the value and reference to next node. The head node points to the first element of the linked list.
The first thing that comes to mind is if we can somehow mark the nodes as visited. If we see a visited node second time, then we can be sure that there is a loop in the list. However, we don’t have any such Boolean flag in a regular Linked List. So if we were to create a special Linked List with Nodes where each node carries an extra Boolean flag, then our solution can work.

As you can imagine, this might not be the best answer.

Secondly, if we can store them in another data structure as we visit them. We use a hashset for this purpose. When we visit a node, we check if it exists in the hashSet. If it doesn’t exist, we add it to the hashset. If it exists then we know that we are in a loop. This is a good solution except the fact that it uses an extra data structure and has a memory complexity of O(n). So this might not be the best solution either.

The most optimal solution is like another question that I discussed previously here.
This is very simple to understand. You can use 2 pointers. Both of them start with the head of the linked list. One moves at regular speed. Other moves at double speed i.e. 2 nodes at a time.
If at any point the slow pointer points to the same element as fast pointer OR fast pointer’s next is pointing to the slow pointer, then we found the loop. Otherwise the fast pointer will reach null before the slow pointer. If it does, then there is no loop in the linked list.
The algorithmic run time complexity of the solution is O(n) where n is the length of the linked list. And the solution doesn’t take any extra space, so space complexity is O(1).
In order to write the pseudo code let’s first define the Node class:

Class Node{
Int value;
Node next;
}

Here is the pseudo code with slowPointer and fastPointer:

Bool IsLoopExist(Node Head){
if(Head == null){
return null
}
slowPointer = Head;
fastPointer = Head;
while(fastPointer!= null){
fastPointer = fastPointer.Next
if(fastPointer!= null){
slowPointer = slowPointer.Next
fastPointer = fastPointer.Next
}
if(slowPointer == fastPointer || slowPointer.Next == fastPointer)
return true;
}
return false;
}

When you write the solution on the whiteboard please make sure to take care of all the edge cases.

The GitHub link to actual working code is available here.
If you follow all these steps then I would say that you have successfully answered the interview question. I will be posting more such interview questions in my upcoming videos. Please make sure to subscribe to my Youtube channel Coach4Dev for more such problems. Until next time, happy coding.