Problem of the week - Loop in a Singly Linked List Ashish Srivastava | @ashishsrtechie | 23 Jan, 2016

John, an interviewee had been working hard for his big day with Yahoo. An interviewer calls him and after a brief introduction, asks him another classic; can you detect a loop in a singly linked list ?
How should have John handled this ?
This classic is also know as cycle detection problem. To learn more about it, refer this wiki link.
Let us discuss the possible solutions.

Approach 1

Hint: Keep track of all the nodes visited

Store all the nodes visited in a hashset or any other preferred data structure and check each node’s existence within this hashset, if found, we have a cycle in the list.

Implementation:

// Data structure to store nodes
HashSet nodeSet = new HashSet();
Node temp = head;
While(temp.next != null)
{
if(nodeSet.contains(temp))
{
return true;
}
else
{
}
temp =  temp.next;

We need to traverse through the node only once, hence time complexity is O(n); however, we do need extra space O(n) to solve through this approach.

Let us see if we can avoid the space complexity.

Approach 2

Implementation:

// Nested traversals
while(temp.next != null)
{
Node temp2 = head;
while(temp2.next != temp)
{
if(temp2 == temp)
{
return true;
}
temp2 = temp2.next;
}
temp =  temp.next;
}

This pseudocode is inefficient because even though it has the space complexity O(1), it has a worst case time complexity of O(n2).

Approach 3

Hint: Detect cycles in two passes

Use two iterators to traverse through the list, one iterating one node at a time and the other iterating 2 nodes at a time. If they both match then, the list is cyclic.

Implementation:

ListNode slow = head, fast = head;
while(slow != null && fast !=null) {
// Slow move 1 node
slow = slow.next;
// Fast moves 2 nodes
if(fast.next != null) {
fast = fast.next.next;
} else {
break;
}
//if slow and fast meet, then there is a loop
if(slow == fast) {
return true;
}
}
return false;

This solution has the time complexity of O(n) and space complexity of O(1). This algorithm is also known as "Floyd’s Cycle-Finding Algorithm".

Though computing is not as expensive as it used to be before, a good programmer must always strive for an efficient answer.

To solve such questions and prepare for coding interviews - log on to firecode.io

Think you have more efficient or better solution? share it in the comments!