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

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

说,有两个不同长度的列表, 合并在一个点 ; 我们如何知道合并点在哪里?

条件:

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

两个合并的链接列表的示例。

如果

  • 通过“不允许修改”是指“你可以改变,但最终应该恢复”
  • 我们可以迭代列表两次

以下algorithm将是解决scheme。

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

 x = a+c y = b+c 

由于我们不知道长度,我们将计算xy而不需要额外的迭代。 你会看到如何。

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

之后,当另一个迭代器到达合并点时,将不会进入公共尾部。 反而会回到之前已经达到合并点的列表的开头! 因此,在到达变更列表的末尾(即另一个列表的前一个开始)之前,他将总共进行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+yz)/2 

解决了这个问题。

帕维尔的答案要求修改列表以及迭代每个列表两次。

这是一个解决scheme, 需要每次迭代两次(第一次计算它们的长度;如果给定的长度,只需要迭代一次)。

这个想法是忽略较长列表的起始条目(合并点不能在那里),以便两个指针距离列表的末尾有一个相等的距离。 然后移动他们,直到他们合并。

 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 

这与我的其他答案是渐近相同(线性时间),但可能有较小的常量,所以可能更快。 但我认为我的另一个答案是更酷。

以下是迄今为止我所见过的最伟大的 – O(N),没有柜台。 在接受采访的时候,我在VisionMap的一个候选SN中得知了这个消息。

build立一个像这样的交互指针:它每次前进到最后,然后跳转到对端列表的开头,依此类推。 创build其中两个,指向两个头。 每次将每个指针前进1,直到它们相遇。 这将在一两次之后发生。

我仍然在采访中使用这个问题,但是要看看需要多长时间才能理解这个解决scheme的工作原理。

那么,如果你知道他们会合并:

说你开始吧:

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

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

现在你有:

 ABC 1-->2-->3 4 5 

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

如果你不能确定它们合并,你可以使用指针值作为指针值,但那不是那么优雅。

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

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

这可能违反了“仅parsing每个列表一次”的条件,但实现了乌龟和兔子algorithm (用于查找循环列表的合并点和循环长度),因此您从列表A开始,并在达到结束你假装它是一个指向列表B的开始,从而创build一个循环列表的外观。 algorithm会告诉你究竟有多less下拉列表A的合并(根据维基百科描述,variables“mu”)。

另外,“lambda”值告诉你列表B的长度,如果你愿意,你可以在algorithm期间(当你redirectNULL链接时)计算列表A的长度。

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

 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 

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

也许我正在简化这个,但只是迭代最小的列表,并使用最后的节点Link作为合并点?

所以, Data->Link->Link == NULL是终点,给Data->Link作为合并点(在列表的末尾)。

编辑:

好的,从你发布的图片中,你可以parsing出两个最小的列表。 用最小的列表可以维护对以下节点的引用。 现在,当你parsing第二个列表时,你需要比较一下引用,以findReference [i]是LinkedList [i] – > Link的引用。 这将给合并点。 有时间用图片解释(在OP上叠加图片上的值)。

你有一个链表(参考如下):

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

你有第二个链表:

1->2->

通过合并列表,引用将如下所示:

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

因此,你映射第一个“较小”的列表(作为合并列表,这是我们正在计数长度为4和主列表5)

循环遍历第一个列表,保持引用的引用。

该列表将包含以下参考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. 

当然,你保留了一个新的指针列表,但这不在规范之外。 然而,第一个列表只被parsing一次,如果没有合并点,第二个列表将只被完全parsing。 否则,它会更快结束(在合并点)。

我已经在我的FC9 x86_64上testing了一个合并案例,并打印每个节点地址,如下所示:

 Head A 0x7fffb2f3c4b0 0x214f010 0x214f030 0x214f050 0x214f070 0x214f090 0x214f0f0 0x214f110 0x214f130 0x214f150 0x214f170 Head B 0x7fffb2f3c4a0 0x214f0b0 0x214f0d0 0x214f0f0 0x214f110 0x214f130 0x214f150 0x214f170 

注意,因为我已经alignment了节点结构,所以当malloc()节点时,地址alignment16个字节,至less看4位。 最小位是0,即0x0或000b。 所以,如果你也在同样的特殊情况(alignment的节点地址),你可以使用这些至less4位。 例如,当从头到尾移动两个列表时,设置访问节点地址的4位中的1或2,即设置一个标志;

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

注意上面的标志不会影响真正的节点地址,只会影响你的SAVED节点的指针值。

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

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

因为这个build议会恢复修改后的节点地址,所以可以认为是“不修改”。

这个解决scheme迭代每个列表只有一次…不需要修改列表太多..虽然你可能会抱怨空间..
1)基本上你在list1中迭代,并将每个节点的地址存储在一个数组中(存储unsigned int值)
2)然后你迭代list2,并为每个节点的地址—>你通过数组search,find匹配或不…如果你这样做,那么这是合并节点

 //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; } 

希望这是一个有效的解决scheme…

这里是天真的解决scheme,没有neeed遍历整个列表。

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

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

说你有两个头(head1和head2)指向两个列表的头。

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

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

这个怎么样:

  1. 如果只允许遍历每个列表一次,则可以创build一个新节点,遍历第一个列表以使每个节点指向该新节点,并遍历第二个列表以查看是否有节点指向新节点(这是你的合并点)。 如果第二次遍历不会导致您的新节点,那么原始列表没有合并点。

  2. 如果允许您不止一次遍历列表,那么您可以遍历每个列表以查找它们的长度,如果它们不同,则省略长列表开始处的“额外”节点。 然后,一次遍历两个列表,find第一个合并节点。

Java中的步骤:

  1. 创build一个地图。
  2. 在列表的两个分支中开始遍历,并将所有遍历的列表的节点放入Map中,使用与节点相关的一些独特的事物(比如节点Id)作为Key,并且在所有的起始处将值设置为1。
  3. 当第一个重复键到来时,递增该键的值(现在说它的值变成了大于1的2。
  4. 获取键值大于1的键,并且应该是两个列表正在合并的节点。

我们可以通过引入“isVisited”字段来有效地解决这个问题。 遍历第一个列表,并将所有节点的“isVisited”值设置为“true”直到结束。 现在从第二个开始,find第一个标志为true的节点,Boom,它是你的合并点。

步骤1:find两个列表的长度步骤2:find差异,并移动最大的列表与差asynchronous骤3:现在这两个列表将在相似的位置。 第4步:遍历列表以find合并点

 //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; } 

使用Map或Dictionary来存储节点的地址和值。 如果地址重读存在于地图/字典中,则该键的值是答案。 我做到了这一点:

 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; }