Answer the question
In order to leave comments, you need to log in
How can I implement a loop search in a singly linked list?
How to use a function to implement a cycle search in a singly directed list?
It would be even better if it was tailored to the class.
class Node(object):
def __init__(self, value, next_node=None):
self.next_node = next_node
self.value = value
def is_circular():
Answer the question
In order to leave comments, you need to log in
class Node(object):
def __init__(self, value, next_node=None):
self.next_node = next_node
self.value = value
def is_circular(self):
head, visited = self, set()
while head is not None:
i = id(head)
if i in visited:
return True
visited.add(i)
head = head.next_node
return False
Why use extra memory?
def is_circular(self):
turtle = self.head
rabbit = self.head
while(turtle and rabbit and rabbit.next):
turtle = turtle.next
rabbit = rabbit.next.next
if turtle == rabbit:
return True
return False
This is where the decoy patching is used :
def find_cycle(lst):
for i, node in enumerate(lst):
if hasattr(node, 'position'):
return node.position
else:
node.position = i
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question