-1

我在 Geeks for Geeks的 Linked List 挑战中做 Remove loop ：

给定一个包含 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)

我不知道我哪里出错了？

4

1 回答 1

2

你的算法不正确。它正确地检测到环路——使用弗洛伊德的环路检测算法，但在哪里slow和fast彼此相遇并不一定是删除链接的地方。

作为旁注：我不会命名给定的参数q......通常将引用命名为 list 的第一个节点head。

我们可以通过将两个引用（如）中的一个重置为 来找到循环的第一个节点，然后让两个引用以相等的速度移动，直到它们再次相遇。然后您找到了属于循环一部分的第一个节点。fasthead

由于我们确实需要循环的最后一个节点（因此我们可以将其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
于 2021-07-20T06:23:11.127 回答