* Detect cycle in a linked list
:PROPERTIES:
:header-args: :session :exports both
:END:

[Also published [[https://programmer.ke/posts/detect_linkedlist_cycle/][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.

#+name: Node definition
#+begin_src python
from dataclasses import dataclass

@dataclass
class Node:
    value: int
    next: 'Node' = None
#+end_src

#+RESULTS:

#+RESULTS: Node definition

The function ~has_cycle(head)~ should return ~True~ if head has a
cycle like below:

#+begin_src python
head1 = Node(1)
second = head1.next = Node(2)
third = second.next = Node(3)
third.next = second
# has_cycle(head1) -> True
#+end_src

#+RESULTS:

It should return false if head does not have a cycle:

#+begin_src python
head2 = Node(1)
second = head2.next = Node(2)
third = second.next = Node(3)
# has_cycle(head2) -> False

#+end_src

#+RESULTS:


** 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.

#+begin_src python
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
#+end_src

#+RESULTS:

=has_cycle= should return =True= for ~head1~,

#+begin_src python
has_cycle(head1)
#+end_src

#+RESULTS:
: True

and =False= for ~head2~

#+begin_src python
has_cycle(head2)
#+end_src

#+RESULTS:
: False

*** 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.

#+begin_src python
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
#+end_src

#+RESULTS:

=has_cycle= should return =True= for ~head1~,

#+begin_src python
has_cycle(head1)
#+end_src

#+RESULTS:
: True

and =False= for ~head2~

#+begin_src python
has_cycle(head2)
#+end_src

#+RESULTS:
: False

*** Analysis
One possible proof that the hare and tortoise are guaranteed to meet
is [[https://stackoverflow.com/a/6110767/1382495][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