💡 Problem Formulation: A linked list is a fundamental data structure used widely in computer science. However, an issue that often comes up with linked lists is the occurrence of cycles, which can cause algorithms to enter into infinite loops. In this context, a cycle occurs when a node’s next pointer points to a previous node in the list. This article showcases five different methods to detect cycles in a linked list, aiming for a Python program that can identify the presence of a loop and return a boolean indicating whether a cycle exists (True or False).
Method 1: Floyd’s Tortoise and Hare Algorithm
The Floyd’s Tortoise and Hare algorithm is a two-pointer technique where one pointer moves at normal speed (the tortoise) and the other moves at twice the speed (the hare). If there is a cycle, they are guaranteed to meet at some point.
Here’s an example:
class ListNode:
def __init__(self, value=0, next=None):
self.val = value
self.next = next
def has_cycle(head):
tortoise, hare = head, head
while hare and hare.next:
tortoise = tortoise.next
hare = hare.next.next
if tortoise == hare:
return True
return False
# Example linked list with a cycle:
# 1 -> 2 -> 3 -> 4 -> 2 ...
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node2
print(has_cycle(node1))The output of this code snippet:
True
The code defines a ListNode class for linked list nodes and a function has_cycle() that implements Floyd’s algorithm. By advancing two pointers at different speeds, it successfully detects the loop when both pointers reference the same node.
Method 2: Hash Table Tracking
Hash table tracking involves storing nodes in a hash table as we traverse the linked list. If we encounter a node that is already in the hash table, it means we have a cycle.
Here’s an example:
def has_cycle(head):
nodes_seen = set()
current = head
while current:
if current in nodes_seen:
return True
nodes_seen.add(current)
current = current.next
return False
# Utilizes the same ListNode class and example linked list from Method 1
print(has_cycle(node1))The output of this code snippet:
True
This method uses a Python set to record nodes as they are visited. If a node is revisited, we know a cycle is present. This simple yet effective approach leverages Python’s built-in data structures.
Method 3: Reverse Link Traversal
By attempting to reverse the linked list, a cycle will prevent completion of the reversal process. If we are able to return to the original head of the list, there is no cycle present.
Here’s an example:
def has_cycle(head):
prev, curr = None, head
try:
while curr:
next_node = curr.next
curr.next = prev
prev, curr = curr, next_node
return False # If reversal completes successfully, no cycle
except:
return True # An exception indicates the presence of a cycle
# Utilizes the same ListNode class and example linked list from Method 1
print(has_cycle(node1))The output of this code snippet:
True
This code attempts to reverse the list by changing the pointers. An exception is likely thrown due to the cycle, triggering the catch block, which returns True, indicating a cycle. Note, however, this method alters the linked list which could be undesirable.
Method 4: Mark Visited Nodes
Another technique is to mark visited nodes by modifying the node’s structure itself. This assumes that we are allowed to change the node’s structure during the algorithm’s runtime.
Here’s an example:
class ListNode:
def __init__(self, value=0, next=None):
self.val = value
self.next = next
self.visited = False
def has_cycle(head):
while head:
if head.visited:
return True
head.visited = True
head = head.next
return False
# Utilizes the modified ListNode class with 'visited' attribute
# This will not work with the previous list due to the changes
# So, create nodes again
node1, node2, node3, node4 = ListNode(1), ListNode(2), ListNode(3), ListNode(4)
node1.next, node2.next, node3.next, node4.next = node2, node3, node4, node2
print(has_cycle(node1))The output of this code snippet:
True
This method adds an attribute visited to each ListNode and marks nodes as visited while traversing. When visiting a node that’s already marked as visited, a cycle is detected. Note, this physically alters the list nodes.
Bonus One-Liner Method 5: Recursive Set Inclusion
This unconventional approach uses recursion and a default mutable argument (a set) to keep track of visited nodes in a compact, one-liner function.
Here’s an example:
def has_cycle(node, seen=set()):
return node in seen or (node and has_cycle(node.next, seen | {node}))
# Will need to recreate the linked list since sets use hashable items
node1, node2 = object(), object()
node1.next = node2; node2.next = node1 # Simplified cyclical linked list representation
print(has_cycle(node1))The output of this code snippet:
True
In this one-liner, we use recursion to traverse the list, adding each node to a set. If we encounter a node that’s already in the set, a cycle exists. An elegant, albeit slightly less efficient, solution.
Summary/Discussion
- Method 1: Floyd’s Algorithm. Strengths: Does not use extra space and has a linear time complexity. Weaknesses: Can be unintuitive to understand at first.
- Method 2: Hash Table Tracking. Strengths: Easy to understand and implement. Weaknesses: Requires additional memory proportional to the number of elements in the list.
- Method 3: Reverse Link Traversal. Strengths: Does not require extra space. Weaknesses: List is modified during processing, may cause issues if the list cannot be altered.
- Method 4: Mark Visited Nodes. Strengths: Easy to implement. Weaknesses: Modifies the original data structure, might not be allowed in certain situations.
- Bonus One-Liner Method 5: Recursive Set Inclusion. Strengths: Very concise and elegant. Weaknesses: Less efficient due to recursion stack space and potentially deep recursion for long lists.