G
G
George1232017-02-22 20:38:13
Python
George123, 2017-02-22 20:38:13

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

3 answer(s)
L
longclaps, 2017-02-22
@Georgy123

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

V
Vlad, 2017-02-22
@d1skort

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

G
gsedometov, 2017-02-22
@gsedometov

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 question

Ask a Question

731 491 924 answers to any question