检查两个链表是否合并。如果合并，在哪里？

这个问题可能很老套，但我想不出答案。

Say, there are two lists of different lengths, 在某一点合并; how do we know where the merging point is?

条件:

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

Example of two merged linked lists.

49743 次浏览
小开

也许我过分简化了这一点，但是只是迭代最小的列表，并使用最后的节点 Link作为合并点？

因此，其中 Data->Link->Link == NULL是终点，将 Data->Link作为合并点(在列表的末尾)。

编辑:

好的，从你发布的图片，你解析两个列表，最小的第一个。使用最小的列表可以维护对以下节点的引用。现在，当您解析第二个列表时，您将对引用进行比较，以查找 Reference [ i ]是 LinkedList [ i ]-> Link 上的引用的位置。这会给出合并点。用图片解释的时间(将值叠加到图片上 OP)。

你有一个链接列表(如下所示的参考文献) :

A->B->C->D->E

您还有第二个链表:

1->2->

With the merged list, the references would then go as follows:

1->2->D->E->

因此，映射第一个“较小”列表(作为合并列表，我们计算的长度为4，主列表为5)

循环遍历第一个列表，维护引用的引用。

The list will contain the following references Pointers { 1, 2, D, E }.

我们现在来看第二个列表:

-> A - Contains reference in Pointers? No, move on
-> B - Contains reference in Pointers? No, move on
-> C - Contains reference in Pointers? No, move on
-> D - Contains reference in Pointers? Yes, merge point found, break.

当然，您可以维护一个新的指针列表，但这并不超出规范范围。但是第一个列表只解析一次，只有在没有合并点的情况下才会完全解析第二个列表。否则，它将很快结束(在合并点)。

小开

这可能违反了“每个列表只解析一次”的条件，但是实现了 龟兔算法(用于查找循环列表的合并点和循环长度) ，所以你从列表 A 开始，当你到达最后的 NULL 时，你假装它是一个指向列表 B 开始的指针，从而创建了一个循环列表的外观。然后，算法会准确地告诉你列表 A 下合并的位置(根据维基百科的描述，变量是“ mu”)。

此外，“ lambda”值告诉您列表 B 的长度，如果您愿意，您可以在算法期间计算列表 A 的长度(当您重定向 NULL 链接时)。

小开

如果你知道他们会合并:

假设你是这样开始的:

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

1) Go through the first list setting each next pointer to NULL.

现在你有了:

A   B   C


1-->2-->3   4   5

2)现在通过第二个列表，等待，直到你看到一个 NULL，这是你的合并点。

如果不能确定它们是否合并，那么可以对指针值使用哨兵值，但这样做不够优雅。

小开
最佳答案

如果

  • “修改是不允许的”，意思是“你可以改变，但最终它们应该被恢复”，以及
  • 我们可以精确地迭代列表 两次

下面的算法就是解决方案。

首先，数字。假设第一个列表的长度为 a+c，第二个列表的长度为 b+c，其中 c是它们的公共“尾巴”的长度(在合并点之后)。让我们将它们表示如下:

x = a+c
y = b+c

Since we don't know the length, we will calculate x and y without additional iterations; you'll see how.

Then, we iterate each list and reverse them while iterating! If both iterators reach the merge point at the same time, then we find it out by mere comparing. Otherwise, one pointer will reach the merge point before the other one.

After that, when the other iterator reaches the merge point, it won't proceed to the common tail. Instead will go back to the former beginning of the list that had reached merge-point before! So, before it reaches the end of the changed list (i.e. the former beginning of the other list), he will make a+b+1 iterations total. Let's call it 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

这样问题就解决了。

小开

这里有一个解决方案，计算速度很快(每个列表迭代一次) ，但需要大量内存:

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
小开

我已经在我的 FC9 x86 _ 64上测试了一个合并案例，并打印了每个节点的地址，如下所示:

Head A 0x7fffb2f3c4b0
0x214f010
0x214f030
0x214f050
0x214f070
0x214f090
0x214f0f0
0x214f110
0x214f130
0x214f150
0x214f170




Head B 0x7fffb2f3c4a0
0x214f0b0
0x214f0d0
0x214f0f0
0x214f110
0x214f130
0x214f150
0x214f170

Note becase I had aligned the node structure, so when malloc() a node, the address is aligned w/ 16 bytes, see the least 4 bits. The least bits are 0s, i.e., 0x0 or 000b. 因此，如果您也是在相同的特殊情况下(对齐的节点地址) ，您可以使用这些至少4位。 For example when travel both lists from head to tail, set 1 or 2 of the 4 bits of the visiting node address, that is, set a flag;

next_node = node->next;
node = (struct node*)((unsigned long)node | 0x1UL);

注意，上面的标志不会影响实际的节点地址，只会影响您的 SAVED 节点指针值。

一旦发现有人已经设置了标志位，那么第一个发现的节点应该是合并点。 完成后，通过清除已设置的标志位来恢复节点地址。但是重要的一点是，在迭代(例如 node = node-> next)执行 clean 时应该小心。记住你设置了标志位，所以这样做

real_node = (struct node*)((unsigned long)node) & ~0x1UL);
real_node = real_node->next;
node = real_node;

因为这个建议将恢复修改后的节点地址，所以可以认为它是“不修改”的。

小开

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

这和我的另一个答案是渐近相同的(线性时间) ，但是可能有更小的常数，所以可能更快。但我觉得我的另一个答案更酷。

小开

如果我们可以迭代列表两次，那么我就可以提供确定合并点的方法:

  • iterate both lists and calculate lengths A and B
  • 计算长度差 C = | A-B | ;
  • 开始同时迭代这两个列表，但是在列表上添加更大的 C 步骤
  • 这两个指针将在合并点相遇
小开

this solution iterates each list only once...no modification of list required too..though you may complain about space..
1)基本上可以在 list1中迭代，并将每个节点的地址存储在一个数组中(该数组存储无符号 int 值)
2)然后迭代 list2，对于每个节点的地址——-> ，在数组中搜索，找到匹配的或不匹配的... ... 如果找到匹配的，那么这就是合并节点

//pseudocode
//for the first list
p1=list1;
unsigned int addr[];//to store addresses
i=0;
while(p1!=null){
addr[i]=&p1;
p1=p1->next;
}
int len=sizeof(addr)/sizeof(int);//calculates length of array addr
//for the second list
p2=list2;
while(p2!=null){
if(search(addr[],len,&p2)==1)//match found
{
//this is the merging node
return (p2);
}
p2=p2->next;
}


int search(addr,len,p2){
i=0;
while(i<len){
if(addr[i]==p2)
return 1;
i++;
}
return 0;
}

希望这是一个有效的解决方案..。

小开

这是一个天真的解决方案，不需要遍历整个列表。

如果结构化节点有三个字段，如

struct node {
int data;
int flag;  //initially set the flag to zero  for all nodes
struct node *next;
};

假设你有两个头(头1和头2)指向两个列表的头。

以相同的速度遍历这两个列表，并将该节点的标志 = 1(访问标志) ,

  if (node->next->field==1)//possibly longer list will have this opportunity
//this will be your required node.
小开

这样吧:

  1. 如果您只允许遍历每个列表一次，那么您可以创建一个新节点，遍历第一个列表以使每个节点指向这个新节点，并遍历第二个列表以查看是否有任何节点指向您的新节点(这是您的合并点)。如果第二次遍历没有导向新节点，那么原始列表就没有合并点。

  2. 如果允许多次遍历列表，那么可以遍历每个列表以查找它们的长度，如果它们不同，则在较长列表的开头省略“额外”节点。然后一次遍历两个列表中的一个步骤，找到第一个合并节点。

小开

您可以使用一组节点。遍历一个列表并将每个节点添加到集合中。然后遍历第二个列表，对于每个迭代，检查 Node 是否存在于集合中。如果是这样，那么您已经找到了合并点:)

小开

以下是迄今为止我所看到的最伟大的-O (N) ，没有计数器。我在 视觉地图的一个候选人 S.N. 面试时得到的。

像这样做一个交互指针: 它每次向前直到结束，然后跳到相反列表的开头，以此类推。 创建两个这样的，指向两个头。 每次将每个指针前进1，直到它们相遇。这将在一次或两次通过后发生。译注:

I still use this question in the interviews - but to see how long it takes someone to understand why this solution works.

小开

Java 步骤:

  1. 创建一个地图。
  2. 在 list 的两个分支中开始遍历，并使用与 Nodes (比如节点 Id)相关的一些惟一的东西作为键将 list 的所有遍历节点放入 Map 中，并在所有节点的起始位置放入 Value 作为1。
  3. 当第一个重复的键出现时，增加该键的值(假设它的值变为2，即 > 1)。
  4. 获取值大于1的 Key，它应该是两个列表合并的节点。
小开

我们可以通过引入“访问”字段来有效地解决这个问题。遍历第一个列表，并将所有节点的“ isVisated”值设置为“ true”，直到结束。现在从第二个开始，找到第一个节点，其中标志为真，繁荣，这是您的合并点。

小开

步骤1: 查找两个列表的长度 步骤2: 找到差异并移动带有差异的最大列表 步骤3: 现在两个列表将处于相似的位置。 Step 4 : Iterate through list to find the merge point

//Psuedocode
def findmergepoint(list1, list2):
lendiff = list1.length() > list2.length() : list1.length() - list2.length() ? list2.lenght()-list1.lenght()
biggerlist = list1.length() > list2.length() : list1 ? list2  # list with biggest length
smallerlist = list1.length() < list2.length() : list2 ? list1 # list with smallest length




# move the biggest length to the diff position to level both the list at the same position
for i in range(0,lendiff-1):
biggerlist = biggerlist.next
#Looped only once.
while ( biggerlist is not None and smallerlist is not None ):
if biggerlist == smallerlist :
return biggerlist #point of intersection




return None // No intersection found
小开 
int FindMergeNode(Node *headA, Node *headB)
{
Node *tempB=new Node;
tempB=headB;
while(headA->next!=NULL)
{
while(tempB->next!=NULL)
{
if(tempB==headA)
return tempB->data;
tempB=tempB->next;
}
headA=headA->next;
tempB=headB;
}
return headA->data;
}
小开

Use Map or Dictionary to store the addressess vs value of node. if the address alread exists in the Map/Dictionary then the value of the key is the answer. 我是这么做的:

int FindMergeNode(Node headA, Node headB) {


Map<Object, Integer> map = new HashMap<Object, Integer>();


while(headA != null || headB != null)
{
if(headA != null && map.containsKey(headA.next))
{
return map.get(headA.next);
}


if(headA != null && headA.next != null)
{
map.put(headA.next, headA.next.data);
headA = headA.next;
}


if(headB != null && map.containsKey(headB.next))
{
return map.get(headB.next);
}


if(headB != null && headB.next != null)
{
map.put(headB.next, headB.next.data);
headB = headB.next;
}
}


return 0;
}
小开

There is no need to modify any list. There is a solution in which we only have to traverse each list once.

  1. 创建两个堆栈，比如 stck1和 stck2。
  2. 遍历第一个列表并推送在 stck1中遍历的每个节点的副本。
  3. 与第二步相同，但是这次遍历第二个列表并推送 stck2中节点的副本。
  4. 现在，从两个堆栈中弹出并检查两个节点是否相等，如果是，则保留对它们的引用。如果没有，那么以前的节点是相等的实际上是合并点，我们正在寻找。
小开

可以有一个简单的解决方案，但将需要一个辅助空间。其思想是遍历一个列表并将每个地址存储在一个散列映射中，现在遍历另一个列表并匹配该地址是否位于散列映射中。每个列表仅遍历一次。没有修改任何列表。长度还不知道。使用的辅助空间: O (n) ，其中’n’是被遍历的第一个列表的长度。

小开

一个 O (n)复杂性的解决方案，但是基于一个假设。

假设: 两个节点都只有正整数。

logic : make all the integer of list1 to negative. Then walk through the list2, till you get a negative integer. Once found => take it, change the sign back to positive and return.

static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {


SinglyLinkedListNode current = head1; //head1 is give to be not null.


//mark all head1 nodes as negative
while(true){
current.data = -current.data;
current = current.next;
if(current==null) break;
}


current=head2; //given as not null
while(true){
if(current.data<0) return -current.data;
current = current.next;
}


}
小开 
int FindMergeNode(Node headA, Node headB) {
Node currentA = headA;
Node currentB = headB;


// Do till the two nodes are the same
while (currentA != currentB) {
// If you reached the end of one list start at the beginning of the other
// one currentA
if (currentA.next == null) {
currentA = headA;
} else {
currentA = currentA.next;
}
// currentB
if (currentB.next == null) {
currentB = headB;
} else {
currentB = currentB.next;
}
}
return currentB.data;
}
小开

我们可以使用两个指针并以这样的方式移动: 如果其中一个指针为 null，我们将它指向另一个列表的头部，另一个也是如此，这样，如果列表长度不同，它们将在第二次传递中相遇。 如果 list1的长度为 n，list2的长度为 m，则它们的差值为 d = abs (n-m)。他们将走完这段距离，在汇合点会合。
Code:

int findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
SinglyLinkedListNode* start1=head1;
SinglyLinkedListNode* start2=head2;
while (start1!=start2){
start1=start1->next;
start2=start2->next;
if (!start1)
start1=head2;
if (!start2)
start2=head1;
}
return start1->data;
}
小开

您可以将 list1的节点添加到一个散列集中，并通过第二个循环添加 list2的节点，如果该集中已经存在任何 list2的节点，则添加该循环。如果是，那么这就是合并节点

static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
HashSet<SinglyLinkedListNode> set=new HashSet<SinglyLinkedListNode>();
while(head1!=null)
{
set.add(head1);
head1=head1.next;
}
while(head2!=null){
if(set.contains(head2){
return head2.data;
}
}
return -1;
}
小开

使用 javascript 的解决方案

var getIntersectionNode = function(headA, headB) {
    

if(headA == null || headB == null) return null;
    

let countA = listCount(headA);
let countB = listCount(headB);
    

let diff = 0;
if(countA > countB) {


diff = countA - countB;
for(let i = 0; i < diff; i++) {
headA = headA.next;
}
} else if(countA < countB) {
diff = countB - countA;
for(let i = 0; i < diff; i++) {
headB = headB.next;
}
}


return getIntersectValue(headA, headB);
};


function listCount(head) {
let count = 0;
while(head) {
count++;
head = head.next;
}
return count;
}


function getIntersectValue(headA, headB) {
while(headA && headB) {
if(headA === headB) {
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
小开

如果允许编辑链表,

  1. 然后将列表2中所有节点的下一个节点指针设置为 null。
  2. 查找列表1中最后一个节点的数据值。 这将为您提供两个列表的单次遍历中的交叉节点，并且“没有高保真逻辑”。
小开

遵循简单的逻辑来解决这个问题: 因为指针 A 和 B 都随 同样的速度移动。为了同时满足这两个点，它们必须覆盖 相同的距离。我们可以通过 将一个列表的长度加到另一个列表实现这一点。


提交答案