Detect a loop in a linked list

Use two pointers: fast and slow. The slow one goes through all elements one by one. The fast one visits each 2nd element only (i.e. jumps to ->next->next).

If the fast pointer reaches the end of the list, then there's no loops. Otherwise both pointers will meet at some point in the loop, hence detecting the loop itself.

Implementation:

boolean isInInfiniteLoop(Node node) {
  if (node == null) {
    return false;
  }
  Node turtle = node; // slower moving node
  Node rabbit = node.next; // faster moving node
  while (rabbit != null) {
    if (rabbit.equals(turtle)) {
      // the faster moving node has caught up with the slower moving node
      return true;
    } else if (rabbit.next == null) {
      // reached the end of list
      return false;
    } else {
      turtle = turtle.next;
      rabbit = rabbit.next.next;
    }
  }
  // rabbit reached the end
  return false;
}

Source: http://eddii.wordpress.com/2006/11/15/detecting-infinite-loop/

To find the node at which the loop starts, one needs to run the above algorithm first and find the intersection point between the turtle and the rabbit. After that we simply do this:

while (rabbit != node) {
  rabbit = rabbit.next;
  node = node.next;
}

(remember that 'node' points to the head of the list.) I.e. the distance between the head of the list and the loop start is equal to the distance between the rabbit and the same loop start.

Complexity:

time O(n)

space O(1)

Links:

• http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm#Tortoise_and_hare