查找链表中的循环(例如破解编码面试的 2.8)

Question

这是在"破解编码面试"一书中的练习2.8之后。在那里，他们要求在链表内找到一个循环。他们提出了一种快速运行/慢运行方法，但我发现了一个更小的解决方案，并希望确认我的解决方案是否存在任何类型的问题。

我决定创建一个最初"all False"的哈希表，用于跟踪节点是否被访问过。然后我做一个循环，直到已经访问了"当前节点"，结束循环：

class Node():
    def __init__(self,data=None,next=None):
        if data!=None:
            self.data=data
        self.next=next
def find_loop(head,hash_table):
    node=head
    while hash_table[node]==False:
        print(node.next.data)
        hash_table[node]=True
        node=node.next
    node_at_beginning_of_loop=node
    return node.data

if __name__ == "__main__":
    import sys
    node3=Node()
    node5=Node(11,node3)
    node4=Node(5,node5)
    node3.data=6
    node3.next=node4
    node2=Node(2,node3)
    node1=Node(9,node2)
    hash_table={}
    for i in range(1,6):
        hash_table[globals()['node%s' % i]]=False
    print(find_loop(node1,hash_table))

Answer 1

您的解决方案将起作用，但就空间而言，这不是一个"高效"的解决方案。 快/慢流道是 O(n( 时间和 O(1( 空间。 您的解决方案是 O(n( 时间和 O(n( 空间。 此外，您应该使用python中的HashSet/set，而不是HashMap/字典。