Problem of the week - Loop in a Singly Linked List

Ashish srivastava 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
    {
       nodeSet.add(temp);
    }
  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

Hint: Two nested traversals to check for nodes already visited

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!