O(1) 时间内的链表连接 [英] Linked List Concatenation In O(1) Time

问题描述

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

I came upon an interesting question and I am puzzled with the answer provided to me. The question is as follows:

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.我很迷惑.任何解释都将是最有帮助的.谢谢.

I initially thought that a DLL would be the correct choice as concatenation can happen from both side, however the answer seems to CLL. I am confused. Any explanation will be most helpful. Thanks.

推荐答案

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

You can easily concatenate two lists in O(1) time using either a single linked list or a doubly linked list, provided that you have a pointer to the last node in at least one of the lists. (And, of course, pointers to the list heads.)

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

You can't do it with an array implementation, because you end up having to allocate more memory and copy the new resulting list to it. Even if the array already has memory allocated, you still have to copy all of the new items to it. So it's either O(m+n) or O(n) (where m and n are the lengths of the individual lists, respectively).

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

With a circularly linked list, you can easily concatenate them in O(1) time. It's just a matter of breaking a link in both lists, and then hooking them together. This assumes, of course, that the order of items isn't especially important.

这篇关于O(1) 时间内的链表连接的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！