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()- 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()
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()- 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()
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()
Pingback: Rebrained! » Blog Archive » Cyclic Linked List – Python function to find the node at the start of the loop
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.
?? ????? ?????? ???????? ??? ?????? ?????? ??? ???? ??????. ??? ??? ???? ??? ??? ???? ????? 21 ???? ?? ????? ????? ?????? ???????. ?? ????? ??? ???? ?? ??? ????, ??? ??? ??? ?? ????? ????? ???. ?? ?????? ?? ????, ??? ????? ?? ????? ?????, ?? ???? ??? ??? ????? ????. ???? ????? ????? ???? ???? ???? ??? ??? ???? ???? ??? ?????? ???? ????? ???????? ???? ???????? ???. ????? ????? ??? ????? ????? ?????? ????. ?? ?? ??? ??? ???? ????? ?? ??? ?? ???? ?????? ????? ???????, ???? ?????? ???? ?????? ???? ???? ?????? ??????????.
https://israelnightclub.com/?????-?????-?????/
https://israelnightclub.com/?????-?????-?????/