Cyclic Linked List – finding the start of the loop using Python

I’d blogged previously about writing a python function to find out whether a linked list is cyclic or acyclic – it’s worth a read before tackling this one.

The challenge here is to return the node that is at the start of the loop given the head node of a cyclic linked list.

A cyclic linked list would look something like this:

A->B->C->D->E->F->C

In the case above, A is the head node, and C is the node at the start of the loop.

Solution

Let’s call x the distance from the head to the start of the loop, and c the number of nodes in the loop.

We kick off a fast and a slow pointer from the head, with the fast pointer going twice as fast as the slow pointer (skipping every other node). By the time the slow pointer gets to the start of the loop, the fast pointer will have a head start of x (the fast pointer is always the same distance from the slow pointer as the slow pointer is from the head).

Given its head start of x, when will the fast pointer catch up to the slow pointer? The fast pointer always needs twice the initial distance from the slow pointer to catch up. Moving forward in the loop, the fast pointer is c-x nodes from the slow pointer, so it needs 2(c-x) nodes to catch up. In that time, the slow pointer will have managed to move c-x nodes away from the start (half what the fast pointer travelled).

The key thing to note here is that both pointers are now x nodes away from the start of the loop looking in a forwards direction. So you’ll see that to find the start of the loop the code below gets the fast and slow pointer to meet in the loop, then walks the slow pointer forward x nodes – the distance from the head to the start.

def startOfCyclicLoop(head):

    """
    >>> e1=Element(1)
    >>> e2=Element(2)
    >>> e3=Element(3)
    >>> e4=Element(4)
    >>> e5=Element(5)
    >>> e1.next=e2
    >>> print startOfCyclicLoop(e1)
    None
    >>> e2.next=e3
    >>> e3.next=e4
    >>> e4.next=e5
    >>> print startOfCyclicLoop(e1)
    None
    >>> e5.next=e3
    >>> print startOfCyclicLoop(e1)
    3
    >>> e5.next=e4
    >>> print startOfCyclicLoop(e1)
    4
    >>> e5.next=e2
    >>> print startOfCyclicLoop(e1)
    2
    """

    slow=head
    fast=head
    while fast!=None and fast.next!=None:
        slow=slow.next
        fast=fast.next.next
        if (fast==slow):
            slow=head
            while (fast!=slow):
                slow=slow.next
                fast=fast.next
            return fast
    return None

class Element:
    def __init__(self,data,next=None):
        self.data=data
        self.next=next
    def __str__(self):
        return str(self.data)

if __name__ == "__main__":
    import doctest
    doctest.testmod()