5 Best Ways to Detect a Cycle in a Linked List Using Python

Rate this post

πŸ’‘ 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.