Rebrained!

More Linked Lists – Acyclic or not?

Another problem in the Programming Interviews Exposed book (see previous post) is to determine whether a Linked List is Acyclic or not.

The most obvious way to do this is to iterate over the list, checking whether the next element is one that you’ve seen before. So as you get to an element, you sweep back from head to current.

def isAcyclic1(head):
    """
    >>> e1=Element(1)
    >>> e2=Element(2)
    >>> e3=Element(3)
    >>> e4=Element(4)
    >>> e5=Element(5)
    >>> e1.next=e2
    >>> e2.next=e3
    >>> e3.next=e4
    >>> e4.next=e5
    >>> isAcyclic1(e1)
    True
    >>> e5.next=e3
    >>> isAcyclic1(e1)
    False
    >>> e5.next=e4
    >>> isAcyclic1(e1)
    False
    >>> e5.next=e2
    >>> isAcyclic1(e1)
    False
    """
    curr=head
    while curr!=None:
        sweeper=head
        while sweeper!=curr:
            if curr.next==sweeper:
                return False
            sweeper=sweeper.next
        curr=curr.next
    return True

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

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

This is an O(n squared) solution. There’s a better way, of course, and here I’ll admit I needed a hint from the book. As soon as I saw something about fast and slow pointers it clicked – it’s quite a clever solution. You start a fast pointer, skipping elements, which if acyclic will get to the end quickly. If cyclic, it will eventually trip over the slow pointer. It turns out to be an O(n) solution. Smart.

def isAcyclic(head):

    """
    >>> e1=Element(1)
    >>> e2=Element(2)
    >>> e3=Element(3)
    >>> e4=Element(4)
    >>> e5=Element(5)
    >>> e1.next=e2
    >>> isAcyclic(e1)
    True
    >>> e2.next=e3
    >>> e3.next=e4
    >>> e4.next=e5
    >>> isAcyclic(e1)
    True
    >>> e5.next=e3
    >>> isAcyclic(e1)
    False
    >>> e5.next=e4
    >>> isAcyclic(e1)
    False
    >>> e5.next=e2
    >>> isAcyclic(e1)
    False
    """
    slow=head
    fast=head
    while fast!=None and fast.next!=None:
        slow=slow.next
        fast=fast.next.next
        if (fast==slow):
            return False
    return  True

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

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