链接列表连接在O（1）时间 [英] Linked List Concatenation In O(1) Time

问题描述

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

  2个列表的并置可以执行O（1）时间。 
应该使用以下哪个列表实现？ 
 
  - 单链接列表
  - 双向链接列表
  - 循环链接列表
  - 链接列表的数组实现
  / pre> 
 
 
我最初认为一个DLL是正确的选择，因为连接可能发生在双方，然而CLL的答案似乎是。 
我很困惑
任何解释将是最有帮助的。 
谢谢。
解决方案
您可以使用单个链表轻松连接两个列表（O（1））一个双向链表，只要您有一个指向至少一个列表中最后一个节点的指针。 （当然也是指针列表头。）
 
 
 
你不能用数组实现，因为最终不得不分配更多的内存和副本新的结果列表给它。即使阵列已经分配了内存，您仍然必须将所有新的项目复制到它。所以它是O（m + n）或O（n）（其中m和n分别是各个列表的长度）。
 
 
 
带循环链表，您可以轻松地在O（1）时间连接它们。这只是在两个列表中打破链接的问题，然后将它们挂在一起。这当然假定项目的顺序并不是特别重要。
 
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
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.
解决方案
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.)

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).

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屋！