Cycle detection

puzzle, algorithm | 06 September 2022

Given a linked list, if there is a cycle, return the start of the cycle. The start of cycle is defined as the place where 2 nodes meet.
If there is no cycle, return -1.

Space \(O(n)\) solution

The natural solution of finding if there is a cycle is to go down the list using .next and store each visited in a hashtable or set. A cycle exists if and only if we reach a node that is already visited.

Space \(O(1)\) solution: Floyd’s tortoise-hare

A famous solution for detecting cycles is attributed to computer scientist Robert Floyd, who also co-designed the Floyd-Warshall algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights.

Image from wikipedia:

  • first trick is to use two iterators, a slow and a fast. The slow one moves one step at a time. The fast one moves two step (or more) at a time. There is a cycle if and only if they meet.
    slow = slow.next
    fast = fast.next.next

If there is no cycle, then we will come out of the while loop as soon as fast exhausts all the linked nodes.

If there is a cycle, then they will meet for sure. This is intuitive: the 2-step is divisible by 1. We use a helper function get_cycle_length to get the cycle length, and break out of the while loop.

However, when fast meets slow, they can meet somewhere (depends on the linked list) that is not the start of the cycle. To get the start of the cycle, we use the

  • second clever trick that is somewhat similar to the first trick: We use two pointers, both start from the origin (head node), with one pointer p1 moves \(||c||\) (length of cycle) steps from the origin first. Then p1 and p2 move in tandem. Because they are exactly \(||c||\) steps apart, then they meet, it has to be the start of the cycle. It is easiler to understand illustrating for yourself with pencil and paper than words.

To get cycle length, we use a helper function cycle_len. The function starts at the meeting place where slow meets fast, which is somewhere on the cycle.

In the end, we return None if cycle length is not updated and return the meeting node if a cycle is detected.

codelinked list cycle detection.py
class Node:
  def __init__(self, x):
    self.val = x
    self.next = None
class Node:
  def __init__(self, x):
    self.val = x
    self.next = None

def has_cycle(head):
  if not head or not head.next:
      return None # edge case
  # helper function to get cycle length    
  def cycle_len(meetingPlace):
    start, steps = meetingPlace, 0
    while True:
      steps += 1
      start = start.next
      if start is meetingPlace:
        return steps

  fast = slow = head
  while fast and fast.next and fast.next.next:
    slow, fast = slow.next, fast.next.next
    if slow is fast:
      p1 = head
      for _ in range(cycle_len(slow)):
        p1 = p1.next # move p1 to ||c|| from the head Node
      p2 = head
      while p1 is not p2:
        p1 = p1.next
        p2 = p2.next 
      return p1
  return None

h = Node(1)
h.next = Node(2)
h.next.next = Node(3)
h.next.next.next = Node(4)
h.next.next.next.next = Node(5)
h.next.next.next.next.next = Node(6)
h.next.next.next.next.next.next = Node(7)
h.next.next.next.next.next.next.next = h.next.next

result = has_cycle(h)
print(result.val)
# 3
g = Node(1)
g.next = Node(2)
g.next.next = Node(3)
g.next.next.next = Node(4)
g.next.next.next.next = Node(5)
g.next.next.next.next.next = Node(6)
g.next.next.next.next.next.next = Node(7)

result = has_cycle(g)
if result:
  print(result.val)
else:
  print("No cycle")
# No cycle

Note that we use is instead of == for testing if linked node is a cycle:

if slow is fast instead of if slow == fast, and while p1 is not p2 instead of while p1 != p2.

This is because linked nodes may have nodes that have the same values, which may not have cycles.

To get the desired return values, we use the following code. If we use print(result), we would have gotten something about function main from the execution because our Node class does not have a str function.

if result:
  print(result.val)
else:
  print("No cycle")

The time complexity is O(n) because we do not have double loops. We have 1 loop in the main function.

The space complexity is O(1) because we use a few pointers only.