用C++合并链表

Question

在一次采访中，我被问到这个问题:两个链表有两个头。在c中有一个合并的链表，其中第二个链表在某一时刻合并到第一个链表中。我们如何确定合并点，以及找到合并点的复杂性是什么？

有人能帮帮忙吗？

Answer 1

O(n)

search = list1->header;
if (mixed->header == list1->header) search = list2->header;

while (mixed->next != search) mixed = mixed->next;

编辑:变量的新名称和一些注释

/* search is what we want to find. Here it's the head of `list2` */
search = list2->header;
/* unless the merging put `list2` first; then we want to search for `list1` */
if (mixed->header == list2->header) search = list1->header;

/* assume (wrongly) that the header for the mixed list is the merge point */
mergepoint = mixed->head;

/* traverse the mixed list until we find the pointer we're searching */
while (mergepoint->next != search) mergepoint = mergepoint->next;
/* mergepoint now points to the merge point */

Answer 2

更新：假设两个链表的Y形连接，正如Steve Jessop的帖子中更好地描述的那样。但我认为对这个问题的描述足够模棱两可，可能有多种解释，这只是其中的一种。

这可以通过一个列表的单次遍历加上另一个列表的部分遍历来完成。换句话说，它是O(n)。

以下是我提出的算法：

创建一个哈希图。(是的，如果没有现成的库，这就是C中的繁忙工作)。键将是指向List1中的项的指针(即头指针和每个链接)。这些值将是表示位置的整数，即到List1头部的距离。

运行List1，跟踪位置，并散列所有指针和位置。

运行List2，跟踪位置，找到出现在hashmap中的第一个指针。

此时，您将知道两个列表共有的第一个节点在List2中的位置。哈希图条目还将包含该节点在List1中的位置。这将很好地标识您的合并点。

Answer 3

你的意思是你有一个Y形，像这样：

list1: A -> B -> C -> D -> E -> F

list2: X -> Y -> Z -> E -> F

其中A .。Z是单链表节点。我们希望找到“合并点”E，它被定义为出现在两个列表中的第一个节点。对吗？

如果是，那么我会将list2 (F)的最后一个节点附加到list2 (X)的第一个节点。这将把list2变成一个循环：

list2 :X -> Y -> Z -> E -> F -> X -> ...

但更重要的是：

list1 :A -> B -> C -> D -> E -> F -> X -> Y -> Z -> E -> ...

这将问题简化为a previously-solved problem，可以在O(n)时间和O(1)额外的存储空间内解决。

但是读一下你的问题，另一种可能性是，“合并”的意思是“插入”。所以你有两个这样的列表：

list1: A -> B -> C

list2: D -> E -> F

然后是另一个完全独立的列表：

list3: A -> B -> D -> E -> F -> C

这一次，A。F是列表中包含的值，而不是节点本身。

如果值完全不同，您只需在list3中搜索D(或者，如果您不知道复制到另一个列表中的是哪个列表，则搜索D和A中的后者)。这似乎是个毫无意义的问题。如果值可以重复，则必须在list3中检查list2的完整序列。但是，仅仅因为你找到了"DEF“并不意味着那就是插入list2的地方--也许"DEF”之前已经在list1中出现了好几次，而你只是找到了其中的第一次。例如，如果我将"DEF“插入到"ABCDEF”中，结果是"ABCDEFDEF"，那么我是在索引3处插入还是在索引6处插入？无从得知，所以这个问题无法回答。

所以，总之，我不理解这个问题。但不管怎样我可能已经回答了。