/
xddxdd
/
Python
Обзор
Документация
Войти
/
xddxdd
/
Python
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
data_structures/linked_list/has_loop.py
62 строки
2 KB
1227haran
Optimized O(n) to O(1) (#11669)
02 окт 2024, 21:07
Не верифицирован
02 окт 2024, 21:07
918fa8b
Код
Авторство
О чём код?
from __future__ import annotations from typing import Any class ContainsLoopError(Exception): pass class Node: def __init__(self, data: Any) -> None: self.data: Any = data self.next_node: Node | None = None def __iter__(self): node = self visited = set() while node: if node in visited: raise ContainsLoopError visited.add(node) yield node.data node = node.next_node @property def has_loop(self) -> bool: """ A loop is when the exact same Node appears more than once in a linked list. >>> root_node = Node(1) >>> root_node.next_node = Node(2) >>> root_node.next_node.next_node = Node(3) >>> root_node.next_node.next_node.next_node = Node(4) >>> root_node.has_loop False >>> root_node.next_node.next_node.next_node = root_node.next_node >>> root_node.has_loop True """ try: list(self) return False except ContainsLoopError: return True if __name__ == "__main__": root_node = Node(1) root_node.next_node = Node(2) root_node.next_node.next_node = Node(3) root_node.next_node.next_node.next_node = Node(4) print(root_node.has_loop) # False root_node.next_node.next_node.next_node = root_node.next_node print(root_node.has_loop) # True root_node = Node(5) root_node.next_node = Node(6) root_node.next_node.next_node = Node(5) root_node.next_node.next_node.next_node = Node(6) print(root_node.has_loop) # False root_node = Node(1) print(root_node.has_loop) # False