Detect Cycle in Linked List

Detecting a cycle in a linked list is a common problem in computer science. It involves determining whether a linked list has a cycle, i.e., whether there is a loop in the list that causes the traversal to repeat indefinitely.

Floyd’s Tortoise and Hare Algorithm

Floyd’s Tortoise and Hare Algorithm, also known as the cycle detection algorithm, is a popular method for detecting cycles in linked lists. The algorithm uses two pointers, a slow pointer (tortoise) and a fast pointer (hare), to traverse the list.

The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle in the list, the two pointers will eventually meet at some point.

Algorithm

The algorithm works as follows:

  1. Initialize two pointers, slow and fast, to the head of the linked list.
  2. Move the slow pointer one step at a time and the fast pointer two steps at a time.
  3. If the fast pointer reaches the end of the list (i.e., fast is None), there is no cycle in the list.
  4. If the slow and fast pointers meet at some point, there is a cycle in the list.

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head: ListNode) -> bool:
    if not head or not head.next:
        return False

    slow = head
    fast = head.next

    while slow != fast:
        if not fast or not fast.next:
            return False

        slow = slow.next
        fast = fast.next.next

    return True

Example

Consider the following linked list with a cycle:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 3

In this case, the node with value 3 is connected back to the node with value 4, creating a cycle in the list.

# Create the linked list
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
node6 = ListNode(6)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node6
node6.next = node3

# Check if the linked list has a cycle
has_cycle(node1) # True

In this example, the has_cycle function returns True since the linked list contains a cycle.

Complexity Analysis

The time complexity of Floyd’s Tortoise and Hare Algorithm is O(n), where n is the number of nodes in the linked list. The algorithm uses two pointers to traverse the list, with the fast pointer moving twice as fast as the slow pointer. If there is a cycle in the list, the two pointers will meet after at most n steps.

The space complexity of the algorithm is O(1), as it only uses a constant amount of extra space for the two pointers.

Summary

Detecting a cycle in a linked list is an important problem in computer science. Floyd’s Tortoise and Hare Algorithm provides an efficient solution to this problem by using two pointers to traverse the list and detect cycles. The algorithm has a time complexity of O(n) and a space complexity of O(1), making it an optimal solution for detecting cycles in linked lists.

Related Posts