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.