找到兩個鏈接列表的合併節點？

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

找到兩個鏈接列表的合併節點？

回答

相關問題