data-structures - O(1) 时间内的链表连接

Question

我遇到了一个有趣的问题，我对提供给我的答案感到困惑。问题如下:

The concatenation of 2 lists can be performed O(1) time. 
Which of the following implementation of list should be used?

 - Singly Linked List 
 - Doubly Linked List
 - Circular Linked List
 - Array Implementation Of Linked List

我最初认为 DLL 将是正确的选择，因为连接可以从双方发生，但答案似乎是 CLL。
我很迷惑。
任何解释都将是最有帮助的。
谢谢。

Answer 1

您可以使用单链表或双链表在 O(1) 时间内轻松连接两个列表，前提是您至少有一个列表中的最后一个节点的指针。 (当然，还有指向列表头的指针。)

你不能用数组实现来做到这一点，因为你最终不得不分配更多的内存并将新的结果列表复制到它。即使数组已经分配了内存，您仍然必须将所有新项目复制到它。所以它要么是 O(m+n) 要么是 O(n)(其中 m 和 n 分别是单个列表的长度)。

使用循环链表，您可以在 O(1) 时间内轻松连接它们。只需断开两个列表中的链接，然后将它们连接在一起即可。当然，这假设项目的顺序不是特别重要。