我目前有一种方法，可以将一个链表（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