Как можно реализовать поиск цикла в однонаправленном списке?

Question

[Georgy123]

Как с помощью функции реализовать поиск цикла в однонаправленном списке?
Еще лучше было бы,если это было подстроено под класс.

class Node(object):
def __init__(self, value, next_node=None):
self.next_node = next_node
self.value = value

def is_circular():

Answer 1

[longclaps]

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

Answer 2

[Влад]

Зачем использовать дополнительную память?

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

Comments

[longclaps]

Поправь вначале
turtle = rabbit = self
у нода нет головы

[Влад]

longclaps: да, спасиб, писал на коленке

Answer 3

[gsedometov]

Тут используется манки-патчинг:

def find_cycle(lst):
  for i, node in enumerate(lst):
    if hasattr(node, 'position'):
      return node.position
    else:
      node.position = i