Detecting Cycle in a Linked List

excerpt: How do we detect a cycle in a linked list? tags: cycle-detection

The easiest way to check if a linked list has a loop is to traverse the nodes, mark each node as you visit it. If you encounter a node that is already marked, you know that the list has a loop and that it start at that node. If there is a restriction that we cannot change the node class, so we cannot add a visited attribute, how do we handle this requirement?

Detecting Cycle in Linked List

The node can be added to a Set during the traversal of the linked list. If a node is already in the set, the list contains a loop that starts at that node. The LinkedList class must have require statement for set class.

1

require 'set'

The cycle? method is implemented as shown below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def cycle?
  visited = Set.new
  current = @head
  
  while current.link
    if visited.include?(current.link)
      return true
    end
    visited.add(current)
    current = current.link
  end
  
  return false
end

The method can be tested with the code:

1
2
3
4
5
6
7
8
9

tail = Node.new(Float::INFINITY, nil)
last = Node.new(14, tail)
second = Node.new(18, last)
head = Node.new(20, second)
sentinel = Node.new(0, head)
tail.link = sentinel

list = LinkedList.new(sentinel)
p list.cycle?

The linked list with no cycle can be tested by not linking the tail to the first node. The line tail.link = sentinel is removed from the previous code.

1
2
3
4
5
6
7
8

tail = Node.new(Float::INFINITY, nil)
last = Node.new(14, tail)
second = Node.new(18, last)
head = Node.new(20, second)
sentinel = Node.new(0, head)

list = LinkedList.new(sentinel)
p list.cycle?

How can we detect loops without using extra storage?