Cycle Detection
Table of Contents
1. Detect cycle in a linked list
Given the head of a linked list, return a boolean indicating whether it has a cycle or not.
A node can be represented as a class with value and a pointer to the next node.
from dataclasses import dataclass @dataclass class Node: value: int next: 'Node' = None
The function has_cycle(head)
should return True
if head has a
cycle like below:
head1 = Node(1) second = head1.next = Node(2) third = second.next = Node(3) third.next = second # has_cycle(head1) -> True
It should return false if head does not have a cycle:
head2 = Node(1) second = head2.next = Node(2) third = second.next = Node(3) # has_cycle(head2) -> False
1.1. First approach: Using a visited set
Iterate through all the nodes of the linked list adding each node to a set indicating that it has been visited. If a visited node is found to already exist in the set, flag a detected cycle.
def has_cycle(head): visited = set() # assuming unique values for each node, use node value to keep track # of visited nodes visited.add(head.value) current = head while current.next: if current.next.value in visited: return True current = current.next visited.add(current.value) return False
has_cycle
should return True
for head1
,
has_cycle(head1)
True
and False
for head2
has_cycle(head2)
False
1.1.1. Analysis
This approach has a space/time complexity of O(n), where n is the number of nodes. The list will have to be traversed at most once, to find cycles. Since we add each visited node to the stack, the memory usage grows by n.
1.2. Second approach: Floyd's Tortoise and Hare
The second approach involves using two pointers iterating the list at different speeds. If there is a cycle, the faster one should catch up to the slower one. If there's no cycle, the faster one will get to the end of the list.
The faster pointer, the hare, iterates the list two steps at a time, while the slower one, the tortoise, iterates it one step at a time.
def has_cycle(head): tortoise = hare = head while hare.next and hare.next.next: hare = hare.next.next tortoise = tortoise.next if hare.value == tortoise.value: return True return False
has_cycle
should return True
for head1
,
has_cycle(head1)
True
and False
for head2
has_cycle(head2)
False
1.2.1. Analysis
One possible proof that the hare and tortoise are guaranteed to meet is here.
Given n nodes, the time complexity is n, whereas the space complexity is O(1) because we only rely on iteration and comparison of the two pointers to detect cycles.