В этой статье блога мы углубимся в различные методы обнаружения циклов в связанном списке. Мы рассмотрим различные подходы, а также примеры кода, для решения проблемы цикла связанных списков в LeetCode. К концу этой статьи вы получите полное представление о различных методах идентификации циклов в связанном списке.

Метод 1: два указателя (алгоритм черепахи и зайца Флойда)
В этом алгоритме используются два указателя, часто называемые «черепахой» и «зайцем». Черепаха делает один шаг за раз, а заяц делает два шага за раз. Если цикл существует, черепаха и заяц в конечном итоге встретятся в одном узле.

def hasCycle(head):
    if not head or not head.next:
        return False

    slow = head
    fast = head.next

    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next

    return True

Метод 2: хеш-набор
Этот подход предполагает использование хеш-набора для отслеживания посещенных узлов. Мы перебираем каждый узел в связанном списке, и если узел уже присутствует в хеш-наборе, это указывает на наличие цикла.

def hasCycle(head):
    visited = set()

    while head:
        if head in visited:
            return True
        visited.add(head)
        head = head.next

    return False

Метод 3: изменение структуры узлов
В этом методе мы изменяем структуру узлов связанного списка, добавляя дополнительный атрибут, например логический флаг, для обозначения посещенных узлов. Этот подход требует изменения исходного связанного списка, что может быть нежелательно в определенных сценариях.

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.visited = False
def hasCycle(head):
    while head:
        if head.visited:
            return True
        head.visited = True
        head = head.next

    return False

Метод 4: алгоритм «Черепаха и заяц» Флойда с длиной цикла
Этот вариант алгоритма «Черепаха и заяц» Флойда не только обнаруживает наличие цикла, но и вычисляет его длину.

def detectCycle(head):
    if not head or not head.next:
        return None

    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            cycle_length = get_cycle_length(slow)
            return find_cycle_start(head, cycle_length)

    return None
def get_cycle_length(slow):
    current = slow
    length = 0

    while True:
        current = current.next
        length += 1
        if current == slow:
            break

    return length
def find_cycle_start(head, cycle_length):
    pointer1 = head
    pointer2 = head

    for _ in range(cycle_length):
        pointer2 = pointer2.next

    while pointer1 != pointer2:
        pointer1 = pointer1.next
        pointer2 = pointer2.next

    return pointer1

В этой статье мы рассмотрели различные методы обнаружения циклов в связанном списке, приведя примеры кода для каждого подхода. Мы рассмотрели алгоритм двух указателей (алгоритм черепахи и зайца Флойда), реализацию хэш-набора, модификацию структуры узла и вариант алгоритма Флойда для расчета длины цикла. Понимая эти методы, вы сможете уверенно решать проблему цикла связанных списков на LeetCode и аналогичных платформах кодирования.

Не забудьте проанализировать требования вашей конкретной проблемы и выбрать наиболее подходящий метод. Приятного кодирования!