# Day 62: Linked-list cycle detection

The task is to detect and repair a singly linked list that contains cycle. And the solution is fast, very simple *and* brilliant.

Here’s an idea. Iterate through the list using two pointers — *slow* and *fast*. Slow pointer iterates node by node, while fast pointer iterates by two nodes. If the pointers meet, there’s a cycle.

Let’s use a bit of math to understand how the algorithm works. Denote

At first, focus on the simplest case — full cycle; linked list where tail points directly to head and `N = C`

.

What is the number of steps the algorithm has to do in this case? We know that *fast* pointer has to iterate twice as many nodes when it meets the *slow* pointer. That leads to the congruence.

In this simple case the pointers meet at *last item*. And if you think about it, it’s an intuitive result.

But what about general case when tail node points to anywhere in the list? Denote `T`

as number of items that are not part of the cycle and focus at the *moment when slow pointer enters the cycle*.

Slow pointer has made `T`

steps, while fast pointer has made `2T`

steps. And since they both are in the cycle, now, they must follow the same congruence as before.

We know that `k`

is the *number of steps made after the slow pointer entered the cycle.* The equation says that if we make `T`

more steps, the slow pointer finishes the cycle and ends up after the last item in the list.

Hence start another slow pointer from head and iterate through the list until these two slow pointers meet. This will be the position that has to be fixed.

https://github.com/coells/100days

https://notebooks.azure.com/coells/libraries/100days

#### algorithm

def detect_cycle(head):

if not head:

return

# cycle detection: 2k = k (mod C)

p, q = head, head.next

while q and p is not q:

p, q = p.next, q.next and q.next.next

if p is q:

# cycle removal: k + T = 0 (mod C)

p = head

while p is not q.next:

p, q = p.next, q.next

# fix the last link

q.next = None

return q

#### utilities

class Node:

def __init__(self, **kwargs):

self.__dict__ = kwargs

def __repr__(self):

return str(self.__dict__)

def linked_list_with_cycle(length, cycle):

head, tail = None, None

for i in range(length):

# prepend head

head = Node(value=length - i, next=head)

tail = tail or head

# make cycle of length C

if i + 1 == cycle:

tail.next = head

return head

#### run

> linked_list = linked_list_with_cycle(10, 4)

> print(linked_list)

{'value': 1, 'next': {'value': 2, 'next': {'value': 3, 'next': {'value': 4, 'next': {'value': 5, 'next': {'value': 6, 'next': {'value': 7, 'next': {'value': 8, 'next': {'value': 9, 'next': {'value': 10, 'next': {...}}}}}}}}}}}

> detect_cycle(linked_list)

{'value': 10, 'next': None}