鏈接列表問題

Question

嗨......

如果我們給出兩個鏈表（可能長度不同），使得從最後幾個節點是常見的...我們如何找到第一個公共節點儘可能少的時間......？

該列表單獨鏈接。有些節點從最後是很常見的，我們需要找到它們之間第一個共同的節點。

Answer 1

假設每個鏈表都有一個完全唯一的集合，我所看到的唯一方法是使用嵌套for循環，這將非常低效。如果數據集是不是唯一的，你可以使用第三方（鏈接）列表，只有獨特的節點的緩存，但你仍然在尋找在澳的最壞情況（N²）

Answer 2

• 計數兩份名單 - 爲O（n ）
• 同時跳過列表長度之間的差的較長列表上
• 遍歷列表，直到發現一個共同的節點 - 爲O（n）

總複雜性：O（n）的

例如：

1-> 2-> 3-> 4-> 7-> 8
--------- 5-> 6-> 7-> 8

我們期望得到，因爲它是第一個通用節點。

1. 計數的清單 - 第一= 6，第二= 4
2. 跳過兩個（6-4 = 2）在第一（較長的）列表元素。
3. 同時迭代
   3.1。 3 == 5是假的
   3.2。 4 == 6是假的
   3.3。 7 == 7是真的，那麼7是公共節點

Answer 3

O（n）解決方案找到具有相同值的列表中的第一個節點。然後您可以從該節點提取值。

除非另有說明，並且沒有嵌套的O(n)操作，否則所有代碼段（註釋）均爲O(1)。因此整個解決方案是O（n）。

它通過計算每個列表中的元素，然後推進最長列表的指針，使兩端對齊。

然後它以同步的方式遍歷兩個列表。如果節點匹配並且先前未匹配，則節點保存該節點（而不是，如果它們匹配，因爲您想在序列中匹配最早的）。

如果它們不匹配，則保存該事實，以便後續匹配將被視爲序列中最早的匹配。

當您到達兩個列表的末尾時，您或者顯示沒有匹配（如果兩個列表的最後一個節點不同）或者序列中最早的匹配。

僞代碼只當然，因爲它的功課：

def findCommonNode (head1, head2): 

    # Work out sizes O(n) 

    set count1 and count2 to 0 

    set ptr1 to head1 
    while ptr1 is not equal to NULL: 
     increment count1 
     set ptr1 to ptr1->next 

    set ptr2 to head2 
    while ptr2 is not equal to NULL: 
     increment count2 
     set ptr2 to ptr2->next 

    # If either size is 0, no match possible. 

    if count1 == 0 or count2 = 0: 
     return NULL 

    # Make the first list longer (or same size). 

    if count1 < count2: 
     swap count1 and count2 
     swap head1 and head2 (local copies only) 

    # Move through longest list until they're aligned O(n). 

    set ptr1 to head1 
    set ptr2 to head2 

    while count1 is greater than count2: 
     decrement count1 
     set ptr1 to ptr1->next 

    # Initially mark as non-match. 

    set retptr to NULL 

    # Process both (aligned) lists O(n). 

    while ptr1 is not equal to NULL: 
     # If equal and if first match after non-match, save position. 

     if ptr1->data is equal to ptr2.data: 
      if retptr is equal to NULL: 
       set retptr to ptr1 
     else: 
      # If not equal, mark as non-match. 

      set retptr to NULL 

     # Advance to next element in both lists. 

     set ptr1 to ptr1->next 
     set ptr2 to ptr2->next 

    # Return the earliest match. 

    return retptr 

比方說，你有兩個列表1,2,3,4,5,5,6,7,8,9和0,6,9,8,9。對齊這些並根據大小差異推進列表1指針，您將獲得：

  v 
1 2 3 4 5 5 6 7 8 9 
      0 6 9 8 9 
     ^

然後將匹配設置爲NULL並開始處理。它們不匹配（5/0），因此您將第一個匹配節點設置爲NULL（即使它已經爲NULL）並且前進到6/6。

這些（6/6）匹配（並且當前匹配爲NULL），因此您將其中一個地址保存爲匹配，然後前進。

7/9不匹配，所以您再次將匹配設置爲NULL，然後前進。

8/8匹配和匹配是NULL，所以你再次將匹配設置爲其中之一，然後前進。

9/9也匹配但匹配已經設置，所以你不會改變它。提前，然後退出這兩個列表中的元素。

然後您返回與8節點之一匹配。這是您最常見的尾部部分。