Skip to content

detect_linkedlist_cycle.org

Latest commit

 

History

History
156 lines (113 loc) · 3.33 KB

detect_linkedlist_cycle.org

File metadata and controls

156 lines (113 loc) · 3.33 KB

Detect cycle in a linked list

[Also published here]

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

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)

and False for head2

has_cycle(head2)

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.

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)

and False for head2

has_cycle(head2)

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.

References

https://stackoverflow.com/a/47203425/1382495

https://stackoverflow.com/a/6110767/1382495

https://en.wikipedia.org/wiki/Cycle_detection