检查两个链表是否合并。 如果是的话，在哪里？
这个问题可能很老，但我想不出答案。
说，有两个不同长度的列表， 合并在一个点 ; 我们如何知道合并点在哪里？
条件：
- 我们不知道这个长度
- 我们应该只parsing每个列表一次。
如果
- 通过“不允许修改”是指“你可以改变，但最终应该恢复”
- 我们可以迭代列表两次
以下algorithm将是解决scheme。
首先，数字。 假设第一个列表的长度为a+c ，第二个列表的长度a+c b+c ，其中c是它们的公共“尾部”（合并点之后）的长度。 让我们把它们表示如下：
x = a+c y = b+c
由于我们不知道长度，我们将计算x和y而不需要额外的迭代。 你会看到如何。
然后，我们迭代每个列表，并在迭代的时候反转它们！ 如果两个迭代器同时到达合并点，那么我们只通过比较就可以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.
这个怎么样：
-
如果只允许遍历每个列表一次，则可以创build一个新节点，遍历第一个列表以使每个节点指向该新节点，并遍历第二个列表以查看是否有节点指向新节点（这是你的合并点）。 如果第二次遍历不会导致您的新节点，那么原始列表没有合并点。
-
如果允许您不止一次遍历列表，那么您可以遍历每个列表以查找它们的长度，如果它们不同，则省略长列表开始处的“额外”节点。 然后，一次遍历两个列表，find第一个合并节点。
Java中的步骤：
- 创build一个地图。
- 在列表的两个分支中开始遍历，并将所有遍历的列表的节点放入Map中，使用与节点相关的一些独特的事物（比如节点Id）作为Key，并且在所有的起始处将值设置为1。
- 当第一个重复键到来时，递增该键的值（现在说它的值变成了大于1的2。
- 获取键值大于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; }
