我目前有一种方法可以将一个链表(list2)附加到另一个链表(list1)的末尾。它通过 while 循环来完成此操作，每次迭代都会将 list1 中的下一个节点附加到 list2 的末尾，依此类推。
我的理解是，这将是 O(n) 时间复杂度，因为 while 循环中的迭代次数直接由 list2 的大小决定。如果list2有15个节点，则该函数执行15次追加，如果list2有1000个节点，则该函数执行1000次追加。
但是，我经常看到人们注意到，如果您保留指向 list1 尾部的指针，则可以以 O(1) 时间复杂度执行此联合。这怎么可能？从我(诚然有限)的理解来看，我可以在某种程度上理解单个追加是 O(1)，但是如果您要追加整个列表，那么它是否不需要在 while 循环中并扫描所有 list2 ，因此O(n)？
最佳答案
这里的关键是您不需要附加整个列表。 list2已经是一个链接列表，每个元素都链接到后面的元素，因此如果您的列表包含对第一个和最后一个元素的引用，那么您真正需要做的就是将它们链接在一起。在伪代码中:
list1.tail.next = list2.head
union.head = list1.head
union.tail = list2.tail
关于algorithm - 对两个无序链表进行并集运算时，时间复杂度能做到O(1)吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/60516216/