检查两个链表是否合并.如果是的话,在哪里？

Question

这个问题可能已经过时了,但我想不出答案.

比如,有两个不同长度的列表,在某一点合并 ; 我们怎么知道合并点在哪里？

条件:

1. 我们不知道长度
2. 我们应该只解析每个列表一次.

Answer 1

到目前为止,以下是我见过的最好的 - O(N),没有计数器.我在VisionMap的候选人SN的采访中得到了它.

创建一个这样的交互指针:它每次前进到结束,然后跳转到相反列表的开头,依此类推.创建其中两个,指向两个头.每次将每个指针前进1,直到它们相遇.这将在一两次通过后发生.

我仍然在访谈中使用这个问题 - 但是看看有多长时间才能理解为什么这个解决方案有效.

Answer 2

Pavel的答案需要修改列表以及迭代每个列表两次.

这是一个解决方案,只需要迭代每个列表两次(第一次计算它们的长度;如果给出长度,你只需要迭代一次).

我们的想法是忽略较长列表的起始条目(合并点不能存在),这样两个指针距离列表末尾的距离相等.然后将它们向前移动直到它们合并.

lenA = count(listA) //iterates list A
lenB = count(listB) //iterates list B

ptrA = listA
ptrB = listB

//now we adjust either ptrA or ptrB so that they are equally far from the end
while(lenA > lenB):
    ptrA = ptrA->next
    lenA--
while(lenB > lenA):
    prtB = ptrB->next
    lenB--

while(ptrA != NULL):
    if (ptrA == ptrB):
        return ptrA //found merge point
    ptrA = ptrA->next
    ptrB = ptrB->next

这与我的其他答案渐近相同(线性时间)但可能具有较小的常数,因此可能更快.但我认为我的另一个答案更酷.

Answer 3

如果

• 通过"不允许修改"这意味着"你可以改变,但最终应该恢复",并且
• 我们可以完全重复两次列表

以下算法将是解决方案.

首先是数字.假设第一个列表具有长度a+c,第二个列表具有长度b+c,其中c是它们的共同"尾部"的长度(在合并点之后).我们将它们表示如下:

x = a+c
y = b+c

由于我们不知道长度,我们将计算x并且y不需要额外的迭代; 你会看到怎么样.

然后,我们迭代每个列表并在迭代时反转它们!如果两个迭代器同时到达合并点,那么我们仅仅通过比较就可以找到它.否则,一个指针将在另一个指针之前到达合并点.

之后,当另一个迭代器到达合并点时,它将不会进入公共尾部.相反,将返回到之前达到合并点的列表的前一个开头!因此,在它到达更改列表的末尾(即另一个列表的前一个开头)之前,他将完成a+b+1迭代.我们称之为z+1.

首先到达合并点的指针将继续迭代,直到到达列表的末尾.它应该计算的迭代次数等于x.

然后,该指针重新迭代并再次反转列表.但现在它不会回到它最初开始的列表的开头!相反,它将进入另一个列表的开头!应该计算它所做的迭代次数并且等于y.

所以我们知道以下数字:

x = a+c
y = b+c
z = a+b

我们从中确定了这一点

a = (+x-y+z)/2
b = (-x+y+z)/2
c = (+x+y-z)/2

这解决了这个问题.

Answer 4

好吧,如果你知道他们会合并:

说你开始:

A-->B-->C
        |
        V
1-->2-->3-->4-->5

1)通过第一个列表设置每个下一个指针为NULL.

现在你有:

A   B   C

1-->2-->3   4   5

2)现在浏览第二个列表,等到看到NULL,这是你的合并点.

如果你不能确定它们是否合并,你可以使用指针值的sentinel值,但这不是那么优雅.

Answer 5

如果我们可以完全重复两次列表,那么我可以提供确定合并点的方法:

• 迭代两个列表并计算长度A和B.
• 计算长度差C = | AB |;
• 开始同时迭代两个列表,但在列表上做更多的其他C步骤
• 这两个指针将在合并点相遇

Answer 6

这是一个解决方案,计算速度快(迭代每个列表一次)但使用大量内存:

for each item in list a
  push pointer to item onto stack_a

for each item in list b
  push pointer to item onto stack_b

while (stack_a top == stack_b top) // where top is the item to be popped next
  pop stack_a
  pop stack_b

// values at the top of each stack are the items prior to the merged item

Answer 7

这可以说违反了"仅解析每个列表一次"的条件,但实现了龟和野兔算法(用于查找循环列表的合并点和循环长度),因此从列表A开始,当你到达NULL时结束你假装它是指向列表B开头的指针,从而创建循环列表的外观.然后,该算法将告诉您合并所在的列表A的确切位置(根据维基百科描述,变量'mu').

此外,"lambda"值告诉您列表B的长度,如果需要,您可以在算法期间计算列表A的长度(当您重定向NULL链接时).

Answer 8

您可以使用一组节点.迭代一个列表并将每个节点添加到集合中.然后遍历第二个列表,并且对于每次迭代,检查集合中是否存在节点.如果有,你找到了你的合并点:)