Finding a loop in a singly linked list - O(n) solution

We can go about this problem in many ways. We will look into few solutions which work in linear time and without adding to space complexity. 

By above problem definition,  list can either be a:

a. Completely reversed list : where last node of the list points to first node of the list.

a->b->c->d->a

b. Randomly looped list: Where some node in the list points to some other node in the list which has already appeared. i.e. list can be like  

a->b->c->d->c

If it is a completely reversed list then we can traverse to the end of list to find out whether last node is same as current node as below. 

public bool IsLooped(Node head){

  Node currentNode = head;

  while (currentNode = currentNode.next()){

    if (currentNode == head) return true;

  }

  return false;

}

Most of the times, interviewer will not expect you to find out full-loops. Instead he will be looking for a solution to find out Randomly looped list. 

We will discuss three solutions numbered based on how good the solution is.

1. "Floyd's Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd.

In this method we traverse the list using two pointers, one moves at double the speed than the other.

We will come across the loop when the fast moving pointer's node is same as the node slow pointer is pointing to. This algorithm works in O(n) time complexity.

This algorithm finds out the loop within one traversal of the entire list.

Algorithm:

a . Slow pointer goes through each node

b.  Fast pointer goes twice fast and checks if the node pointed by fast node and node next to it is same as node pointed slow pointer. If it is same then it means we found the loop. Easy as it reads.

Below code snippet is from link that is from reference mentioned at the end of this article:

// Best solution

public bool hasLoop(Node startNode){

  Node slowNode = startNode;  Node fastNode1 = startNode; Node fastNode2 = startNode;

  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){

    if (slowNode == fastNode1 || slowNode == fastNode2) return true;

    slowNode = slowNode.next();

  }

  return false;

}

2. This solution is by Ostermiller. Here we will have to traverse the list thrice to find out the loop. Hence it works in linear time.

Algorithm :

a. Keep the check node to null and initialize two variables since to 0 and sinceScale to 2.

b. Keep moving the current node to next node till since is less than or equal to sinceScale.

This step assures current node is moved thrice and each time it is checked with checknode if there is a loop.

This step will check each node to which current node moved in those iterations with checknode.

c. Change the check node in next while iteration to node pointed to by current node and repeat step -2.

Reset 'since' to 0 once checknode is modified. This is to allow current node to be checked with new checknode in each iteration while since < sinceScale ,keeping the checknode constant during these iterations.

public bool hasLoop(Node startNode){

  Node currentNode = startNode;

  Node checkNode = null;

  int since = 0;

  int sinceScale = 2;

  do {

    if (checkNode == currentNode) return true;

    if (since >= sinceScale){

        checkNode = currentNode;

        since = 0;

        sinceScale = 2*sinceScale;

    }

    since++;

  } while (currentNode = currentNode.next());

  return false;

}

3. Reversing the list: This solution is valid when problem states list can be modified. This is a brute force approach where we remember the initial node and start reversing the list, if we get back to the initial node that means there is a loop. Note: Use it only when interviewer is good with modifying the list.

References:

This is a nice article which covers finding out a loop in detail. All code snippets are picked from this website. http://ostermiller.org/find_loop_singly_linked_list.html . Thanks!