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()
This entry was posted in programming and tagged , , . Bookmark the permalink.

3 Responses to Linked List – Cyclic or Acyclic?

  1. Pingback: Rebrained! » Blog Archive » Cyclic Linked List – Python function to find the node at the start of the loop

  2. Jasus says:

    Thanks for the nice and simple exalmpe. You’re just missing one crucial piece of information:comparator should specify a custom comparison function of two arguments (list items) which should return a negative, zero or positive number depending on whether the first argument is considered smaller than, equal to, or larger than the second argument.See note 8 under of the official python documentation.

  3. DanielTooms says:

    ?? ????? ?????? ???????? ??? ?????? ?????? ??? ???? ??????. ??? ??? ???? ??? ??? ???? ????? 21 ???? ?? ????? ????? ?????? ???????. ?? ????? ??? ???? ?? ??? ????, ??? ??? ??? ?? ????? ????? ???. ?? ?????? ?? ????, ??? ????? ?? ????? ?????, ?? ???? ??? ??? ????? ????. ???? ????? ????? ???? ???? ???? ??? ??? ???? ???? ??? ?????? ???? ????? ???????? ???? ???????? ???. ????? ????? ??? ????? ????? ?????? ????. ?? ?? ??? ??? ???? ????? ?? ??? ?? ???? ?????? ????? ???????, ???? ?????? ???? ?????? ???? ???? ?????? ??????????.
    https://israelnightclub.com/?????-?????-?????/
    https://israelnightclub.com/?????-?????-?????/

Leave a Reply

Your email address will not be published. Required fields are marked *