Loop Detection

Given a linked list which might contain a loop, implement an algorithm that returns the node at the beginning of the loop (if one exists).

Solution

To detect if a linked list has a loop, we can use two pointers which advance at different rates. This technique is sometimes called the “runner” technique. Observe the diagram below for proof. If you advance the fast runner 2 elements at every increment, and the slow runner 1 element at every increment, the runners will eventually meet.

To identify the node which begins the loop, we can do some quick math using the diagram above. Let’s say that when the slow pointer enters the loop, it will have travelled \(k\) steps, and the fast runner will have travelled \(2k\) steps. Let’s also define the length of the loop as \(L\).

When the slow runner enters the loop, the fast runner will be \(L - k\) steps behind. In the loop, the fast runner catches up to the slow runner at a rate of one step per increment. Therefore, the runners will meet after \(L - k\) increments. This also means that the runners will be \(k\) nodes from the beginning of the loop when they meet.

To find the starting node of the loop, we can move one pointer to the beginning of the linked list, and keep the other pointer at the location of the collision. We will advance the pointers at the same rate, and this time they will collide at the start node of the loop.

Implementation

First, let’s build a function to find the colliding node.

def find_collision(node):
  slow = node
  fast = node

  while(slow.next != None and fast.next.next != None):
    slow = slow.next
    fast = fast.next.next

    if(slow == fast):
      return slow

  else:
    return None

Next, let’s build a function to identify the node which starts the loop.

def find_loop_start(node):
  collision = find_collision(node)

  if(collision is None):
    return None

  first = node
  second = collision

  while(first != second):
    first = first.next
    second = second.next

  return first