logo标签列表

在O(1)时间内连接链表

data-structureslinked-listtime-complexity
9

我遇到了一个有趣的问题，但是对于给我的答案感到困惑。问题如下：

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。 我很困惑。 任何解释都将非常有帮助。 谢谢。

你可以使用任何使用指针的实现方式，并且可以在一次操作中到达最后一个元素，以O(1)的时间复杂度完成。循环链表允许您从头元素返回以到达末尾，然后更新一些指针即可完成。但是，如果您只有一个指向最后一个元素的成员，那么您也可以使用任何其他基于指针的实现方式。 - Donnie
1
问题本身没有提供足够的信息来回答。这取决于您可以多快地访问列表的尾部，并且单链表，双链表和循环链表都可以以不同的方式实现，有些方式可以快速访问尾部，而有些方式需要遍历整个列表才能实现。 - user2357112
另外，基于数组的实现并不是链表。 - user2357112
1
@user2357112：循环链表的“尾”在哪里？而且你可以在数组中实现链表。节点指针只是数组中的索引。 - Jim Mischel
@JimMischel：无论哪个节点代表最后一个元素。链接结构可能没有开始或结束，但我们通常仍然有一个起点的概念。 - user2357112
关于节点指针作为数组索引的问题，你当然可以这样做，但此时你只是在模拟内存。你可以用这种方式在数组中实现任何数据结构。我认为问题所说的实现方式不是这种方式，它听起来更像是标准动态数组实现。 - user2357112
5个回答
11
使用单链表或双向链表，只要你至少拥有一个列表中最后一个节点的指针（当然，还需要列表头的指针），就可以在O(1)时间内轻松地连接两个列表。但是，使用数组实现无法完成此操作，因为您最终需要分配更多的内存，并将新生成的列表复制到其中。即使数组已经分配了内存，您仍然需要将所有新项复制到其中。因此，它的时间复杂度为O(m+n)或O(n)（其中m和n分别是各个列表的长度）。使用循环链接列表，您可以在O(1)的时间内轻松地连接它们。这只是简单地断开两个列表中的链接，然后将它们连接在一起。当然，这假设项目的顺序并不特别重要。
3
答案是循环双向链表。
要合并列表，您需要将第一个列表的最后一个节点的下一个指针指向第二个列表的第一个节点。为了以O(1)时间完成此操作，可以使用循环双向链表。您可以通过head1->next->previous访问第一个列表的最后一个节点，并修改该字段指向head2->next。还要修改head2->next->previous为head1->next。
如果在单向和双向链表中给出任一列表的最后一个节点的指针，则可以在O(1)中合并两个列表。
2

看起来有多个正确的答案。

只要存储链表的第一个和最后一个元素的指针，就可以在O（1）时间内连接两个单向链表。您只需将第一个列表的最后一个元素的下一个指针重新连接到第二个列表的第一个元素即可。这对双向链表也适用。

通过使用类似的技巧，您还可以在O（1）时间内连接两个循环链接的列表。

唯一不起作用的选项是基于数组的列表。

希望这可以帮助！

1
你不需要一个last，但是你需要一个next 假设每个列表至少有两个元素
void merge( node* first, node* second )
{
  node * first_next = first->next;
  node * second_next = second->next;

  first->next = second_next;
  second->next = first_next;
}

正如Jim Mischel所说，任何列表都能正常工作。

谢谢，我一直在寻找某种代码或图表。你提供了我所需要的。 经过阅读多篇文章后，我仍然有疑问。你的代码帮助我理解了它。 - HARDY8118
你真的尝试过这个吗？据我理解，这只是交换了每个列表的第一个元素，而没有进行实际的连接。 - Paul Stelian
0

这两个：

  • 双向链表
  • 循环链表

都是正确的答案。它们都支持O(1)的连接操作。

1
双向链表不正确，因为需要O(n)次迭代才能找到最后一个节点。正确的答案是： 循环链表。 - Aerious
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接