Дано: head - начало связного списка.
Нужно определить, есть ли цикл в связном списке. Цикл в связном списке есть, если существует узел в списке, к которому можно вернуться, последовательно следуя указателям на следующий узел. Внутренне, pos используется для обозначения индекса узла, к которому подключен указатель на хвост. Обратите внимание, что pos не передается в качестве параметра.
Функция должна вернуть True, если в связном списке есть цикл. В противном случае, вернуть False.
Например, у нас есть связный список 1 -> 2 -> 3 -> 4 -> 2, то это означает, что есть цикл в связном списке, так как узел со значением 2 может быть достигнут снова, последовательно переходя по указателям на следующий узел.
Для решения этой задачи можно использовать алгоритм "быстрый заяц и медленная черепаха" (Floyd's cycle-finding algorithm). Алгоритм заключается в том, чтобы использовать два указателя, один быстрый (быстрый заяц), который двигается по списку на два узла за одну итерацию, и один медленный (медленная черепаха), который двигается на один узел за итерацию. Если в связном списке есть цикл, то быстрый указатель рано или поздно догонит медленный указатель.
Допустим, у нас есть связный список 1 -> 2 -> 3 -> 4 -> 2. Медленный указатель начинает с узла 1, а быстрый указатель начинает с узла 2. На первой итерации медленный указатель двигается на узел 2, а быстрый указатель двигается на узел 4. На второй итерации медленный указатель перемещается на узел 3, а быстрый указатель перемещается на узел 2. На третьей итерации медленный указатель перемещается на узел 4, а быстрый указатель перемещается на узел 4. Медленный указатель и быстрый указатель встречаются на узле 4, что означает, что в связном списке есть цикл.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def hasCycle(self, head: ListNode) -> bool:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False