Блог

Я выполнял задачу «Удалить цикл в связанном списке» для вундеркиндов для вундеркиндов:

Задан связанный список из N узлов, такой, что он может содержать цикл.

Цикл здесь означает, что последний узел списка ссылок подключен к узлу в позиции X. Если в списке ссылок нет цикла, X=0.

Удалите цикл из связанного списка, если он присутствует.

Я попробовал использовать этот код:

 class Solution:
    def removeLoop(self, q):
        slow,prev = q,None
        fast = q
        while slow and fast and fast.next:
            prev = fast
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                print(prev.data)
                prev.next = None
                return
 

Но это работает неправильно не во всех случаях.

Например, он удаляет неправильную ссылку, когда это список входных данных:

  1 → 2 → 3
     ↑   ↓
     └── 4
 

В этом случае он удаляет ссылку со 2 по 3, в то время как он должен удалить ссылку с 4 по 2.

Вот код для воспроизведения проблемы:

 class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Solution:
    def removeLoop(self, q):
        slow,prev = q,None
        fast = q
        while slow and fast and fast.next:
            prev = fast
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                print(prev.data)  # Outputs 2, but should output 4
                prev.next = None
                return

# Create list 1 -> 2 -> 3 -> 4 
one = Node(1)
two = Node(2)
three = Node(3)
four = Node(4)
one.next = two
two.next = three
three.next = four
# Add a link from last node to second node
four.next = two  # cycle

Solution().removeLoop(one)
 

Я не знаю, где я ошибся?

Ваш алгоритм неверен. Он правильно определяет цикл-используя алгоритм обнаружения циклов Флойда, но место, где slow они fast встречаются, не обязательно является местом, где нужно удалить ссылку.

В качестве примечания: я бы не стал называть данный аргумент q … Обычно называют ссылку на первый узел списка head .

Мы можем найти первый узел цикла , сбросив одну из двух ссылок (например fast ) на head , а затем позволить обеим ссылкам двигаться с одинаковой скоростью, пока они снова не встретятся. Затем вы нашли первый узел, который является частью цикла.

Поскольку нам действительно нужен последний узел цикла (чтобы мы могли установить его next атрибут None ), нам нужно разорвать этот второй цикл на один шаг раньше:

 def removeLoop(self, head):
    slow = head
    fast = slow
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if fast == slow:
            # Detected the cycle, but still need to find last node:
            fast = head
            while fast.next != slow.next:
                fast = fast.next
                slow = slow.next
            slow.next = None
            return
 

Однако, если цикл включает головной узел, то мы уже слишком поздно выходим из этого цикла «на один шаг раньше». Вот почему я бы предложил добавить фиктивный узел в список и сделать его временным главой. Таким образом, мы уверены, что этот головной узел не является частью цикла, и мы не будем «слишком поздно».:

 def removeLoop(self, head):
    slow = Node(None)   # A dummy node
    slow.next = head    # Prepend it to the list
    head = fast = slow  # ...and start there
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if fast == slow:
            fast = head
            while fast.next != slow.next:
                fast = fast.next
                slow = slow.next
            slow.next = None
            return