找到两个链接列表的合并节点？

MergePoint (LinkList list1, LinkList list2){ 
p = list1.head; 
q = list2.head; 
while (p.next!=null && q.next!=null){ 
    if (p.next == q.next){ 
     System.out.print(p.value + " is the Merging node"); 
     return; 
    } 
    p=p.next; 
    q=q.next; 
}

}找到两个链接列表的合并节点？

我试图解决一个问题，找出2个链表合并节点。在研究其他解决方案之前，我决定编写我的代码，然后与其他现有解决方案进行比较。这里采用的方法是找到两个列表指针都指向的公共节点。你是否同意这条代码或者有什么我不知道在这里？

来源

2012-02-17 Naveen

这是一门功课的问题吗？ – joshhendo 2012-02-17 22:34:07

我喜欢帮助家庭作业问题 - 为什么不呢？ – Irfy 2012-02-17 22:36:03

它不会工作。 – 2012-02-17 22:49:51

您的代码仅适用于两个列表中合并节点位于相同位置的特殊类别的情况。我不认为有一个简单的，子为O（n^2）做到这一点的方法 - 换句话说，你需要一个列表的每一个节点进行比较，与每一个下一秒名单，副反之亦然。

MergePoint (LinkList list1, LinkList list2) { 
    p = list1.head; 
    while (p != null) { 
     q = list2.head; 
     while (q != null) { 
      if (p == q){ 
        System.out.print(p.value + " is the Merging node"); 
        return; 
      } 
      q = q.next; 
     }   
     p = p.next; 
    }  
}

来源

2012-02-17 22:38:39 Irfy

谢谢。感谢帮助！ – Naveen 2012-02-18 03:04:03

@ user664174您的编辑被拒绝是因为它完全改变现有解决方案没有任何意义 - 如果与其他任何建议不同，您应该添加自己的解决方案。 – Irfy 2013-06-09 21:42:13

我认为在这个解决方案中，复杂度应该是O（n * m），因为你不能假设两个链表都有相同的长度。 – 2017-04-16 03:29:11

这只会在“合并节点”位于列表中的相同位置时起作用。

例如，假设您有两个链表...

表1有5个节点（节点A，B，C，d，E）清单2有6个节点（节点V，W， X，Y，C，d）

显然共用节点C.你似乎在寻找你的代码是什么指向普通节点的节点（不知道是不是真的有一个名字，所以在这种情况下，您正在寻找A和Y.

您的代码将执行如下操作：

A.next == V.next? no 
B.next == W.next? no 
C.next == X.next? no

等等等等。这是格式为[元素从元素列表，从列表相比1〜2]

你真正想做的是与清单2.所有元素对比清单1中的第一个元素之后，如果你不这样做找到它，比较列表1的第二个元素和列表2的所有元素，并继续这样做等等。因为这听起来像一个家庭作业问题，我不会给你答案（但我会给你一个提示：你可能需要嵌套循环），但如果你有任何进一步的问题实施它，然后问远。

而且，可能想看看在头节点的特殊情况下，如果在任一列表中的第一个节点是公共节点。在这种情况下，你只是比较“下一个”节点，这意味着如果它是两个列表中的任何一个之间的公共节点，第一个节点就不会匹配。

来源

2012-02-17 22:39:33 joshhendo

谢谢！我寻找的问题范围非常小，我想到的问题实例与您所描述的完全相同。在这种情况下，我将使用第一个列表的外部循环和第二个列表的内部循环，然后进行比较。但是你提到了“比较元素”与“比较下一个指针”？它比较下一个指针的权利？因为元素可以在列表中重复。 – Naveen 2012-02-18 02:59:47

元素是实际的对象，下一个指针是一个指向元素（或对象，在这个例子中是相同的东西）的指针。 – joshhendo 2012-04-28 01:32:18

想到三种解决方案。

首先，嵌套循环Irfy公布。它使用常量内存但是O（N * M）时间，其中N和M是两个列表的长度。

其次，你可以通过把一个列表的每一个节点到HashSet的第一，随后走到另一张单子，做查找到HashSet的以空间换取时间。因为这个查找是O（1），所以总的时间是O（N + M）（构建哈希表和走另一个列表）。然而，折衷是表格所需的O（N）空间。第三，如果允许您至少暂时修改数据，您可以将其中一个列表循环（通过将其最后一个节点的下一个指针连接到第一个节点），然后使用Stepanov描述的算法编程元素用于解决O（N + M）时间和O（1）空间中的问题，因为您知道其中一个列表现在是圆形的，而另一个是P形的：它从它自己的部分开始并最终击中另一个列表的圆圈。它命中的地方称为连接点，Stepanov给你一个算法来找到它。最后，你只需再次解除最后一个节点。

有问题的算法在样章实际可用的，你可以在这里下载：

http://www.elementsofprogramming.com/book.html

来源

2013-06-11 12:52:53

找到两个链接列表的合并节点？

回答

相关问题