给定两个列表 l1,l2，说明如何在 O(1) 时间内合并它们。列表的数据结构取决于您如何设计它。通过合并，我的意思是说列表的并集。
例如:List1 = {1,2,3} list 2 = {2,4,5}
合并列表 = {1,2,3,4,5}
最佳答案
关于“合并”两个排序列表
在 O(1) 中，将两个排序列表合并为一个排序列表显然是不可能的。
你能做的最接近的事情是有一个“惰性”合并，它可以按需提取 O(1) 中的每个连续元素，但要执行完整合并，它仍然是 O(N)(其中 N 是元素的数量)。
您可以做的另一件事是物理上将两个列表首尾相连地合并到一个列表中，不执行 merge algorithm无论如何，这样一个列表中的所有元素都出现在另一个列表中的所有元素之前。这实际上可以在 O(1) 中完成(如果列表维护头指针和尾指针)，但这不是传统定义的合并。
O(1) 中的集并集
如果问题是关于哪种集合表示形式允许在 O(1) 中进行并集运算，那么是的，这实际上是可以做到的。有很多set representation在实践中可能，每个都有一些优点和缺点。
这种专门表示的一个重要示例是 disjoint-set data structure ，它允许 O(α(n)) 基本 Union 和 Find 操作的摊销时间。 α 是 Ackermann function 的倒数;当 Ackermann 函数增长极快时，其反 α 增长极慢。不相交集数据结构本质上为任何实际大小提供了分摊的 O(1) 操作。
注意这里“不相交”是一个关键:它不能表示两个集合{1, 2, 3}和{2, 4, 5}，因为这些集合不是不相交的。不相交的集合数据结构表示许多集合(不仅仅是两个)，但不允许两个不同的集合有共同的元素。
另一个非常实用的集合表示是 bit array ，其中元素映射到位索引，0/1 分别表示不存在/存在。使用这种表示，并集只是按位或；按位交集 AND。渐近地，这不是最佳表示，但在实践中它可以是高性能的集合表示。
关于c - 如何在 C 中以 O(1) 时间合并两个链表？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3488117/