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}
One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.