我正在解决一个leetcode问题，以便在链表中找到交点。当我使用列表时，它会给我超过时间限制的错误，但当我使用set时，它就会给我答案。由于LinkedList中的每个节点都不同，集合和列表都将具有相同的元素
下面是我的代码
def getIntersectionNode(self, headA: ListNode, headB: ListNode):
nodes = set()
while headA != None:
nodes.add(headA)
headA = headA.next
while headB != None:
if headB in nodes:
return headB
headB = headB.next
return None
使用列表而不是集合时发生错误的原因是什么。
在python中，检查集合是否包含某个元素的速度更快。如果nodes是一个集合，则以下操作将更快。
if headB in nodes:
但例如，对集合进行迭代要比对列表进行迭代慢。
in运算符对集合和列表的实现方式不同。
-
对于列表，代码必须遍历整个列表来检查每个元素，这可能是一个线性时间操作。
-
对于一个集合，代码在恒定时间内(平均(使用其哈希代码检查给定元素是否存在。
假设A有m节点，B有n个节点，并且列表不相交(最坏情况(。如果nodes是一个列表，则对于B中的每个节点，该算法必须在a的所有节点上迭代，给出时间复杂度θ(m×n(。相比之下，当使用集合时，时间复杂度将为θ(m+n(。对于m和n的大值，这会在函数的运行时产生很大的差异。
以下是一些关于哈希表(Python的set和dict数据结构的基础(如何工作的参考：
- https://towardsdatascience.com/hash-tables-explained-5dc457db50da?gi=6cce0c91f791
- https://en.wikipedia.org/wiki/Hash_table