对两个无序链表进行并集运算时，时间复杂度可以为O(1)吗？
When performing a union operation on two non-ordered linked lists, can the time complexity be O(1)?
我目前有一种方法可以将一个链表 (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 已经 一个 linked 列表，每个元素 linked 到以下元素，因此如果您的列表包含对第一个和最后一个元素的引用，您真正需要做的就是 link 他们在一起。在伪代码中：
list1.tail.next = list2.head
union.head = list1.head
union.tail = list2.tail
我目前有一种方法可以将一个链表 (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 已经 一个 linked 列表，每个元素 linked 到以下元素，因此如果您的列表包含对第一个和最后一个元素的引用，您真正需要做的就是 link 他们在一起。在伪代码中：
list1.tail.next = list2.head
union.head = list1.head
union.tail = list2.tail