0

所以我知道弗洛伊德的循环检测算法，但是在研究这个问题时，我想出了另一个解决它的想法。

如果我们可以在遍历链表时将每个节点的“ nextpointer ”存储在向量/列表中，如果任何元素的频率大于1，则计数。如果向量/列表中的任何值出现不止一次，则基本上意味着单个节点已被指向两次（或更多），因此它变成了一个循环。

我无法在 Python 3 中编写相同的代码。如果你们能帮助我，我将不胜感激。谢谢。

class Node:
    head = None

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

def findMergeNode(head1, head2):
    a = set()
    b = set()
    while (head1 and head2):
        a.add(head1)
        head1 = head1.next        
        b.add(head2)
        head2 = head2.next
    if (a.intersection(b)):
        return a.intersection(b)
4

1 回答 1

0

您提出的算法将起作用，但是

  1. 它需要O(n)空间，并且
  2. 在列表（向量）中查找需要O(n)时间

第二个可以通过使用集合来解决，但第一个仍然是一个主要缺点。

这是一个带有集合的基本实现：

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

    def add(self, val):
        self.next = Node(val)
        return self.next  # to allow chaining

    def hascycle(self):
        node = self
        visited = set()
        while node:
            if node in visited:  # been here before!
                return True
            visited.add(node)
            node = node.next
        return False

# Demo graph: a -> b -> c -> d -> e -> b
a = Node("a")
e = a.add("b").add("c").add("d").add("e")
# make a back reference from e to b:
e.next = a.next
print(a.hascycle())  # True

注意 的大小如何visited变成与链表本身相同的数量级。当然，当没有检测到循环时，对所有节点的引用都存储在集合中。

Floyd 算法的美妙之处在于它只使用常量空间（当然不包括列表本身）。所以与链表的大小无关，它总是会使用相同数量的空间来进行操作。

于 2020-10-03T12:17:36.880 回答