Linked List – Cyclic or Acyclic?

Another problem in the Programming Interviews Exposed book (see previous post) is to determine whether a Linked List is cyclic 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. 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()