兩個鏈接列表的交集

給定兩個排序鏈接列表L1和L2，計算它們的交點的解決方案L1交叉點L2。兩個鏈接列表的交集

2010-01-31 AJ.

SO的目的是灌輸知識和理解，而不是給你模糊問題的完整解決方案。 – 2010-02-02 22:24:22

L1_node = L1.head; 
L2_node = L2.head; 
Result = new SList; 
while L1_node != NULL and L2_node != NULL: 
    if L1_node.value == L2_node.value: 
    Result.append(L1_node.value) 
    L1_node = L1_node.next 
    L2_node = L2_node.next 
    elif L1_node.value < L2_node.value: 
    L1_node = L1_node.next 
    else 
    L2_node = L2_node.next

（翻譯到C自己）

來源

2010-01-31 11:19:01 kennytm

這是一個錯誤。在==情況下，你不會跳過任何東西 - 你會得到無限的L1_node.value系列。 – Steve314 2010-01-31 11:26:51

也許它是作爲OP的調試練習而留下的？如果我要僱用一個人，並提出了這個確切的面試問題，並得到了這個確切的解決方案，我會質疑他作爲程序員開始工作的動機，如果他只是簡單地將他在網上找到的答案撇在一邊。 – 2010-01-31 11:40:26

@Lasse - 也許，並不是一個壞主意。我的下面的錯誤是故意的，誠實的<隱藏在公然謊言中的羞恥>。 – Steve314 2010-01-31 11:51:19

-1

的基本方法，以按順序合併樣的算法是，你永遠需要考慮在同一時間超過三個項目 - 從每個輸入前項列表，以及潛在的保存結果。

在這種情況下，我會用...

loop forever 
    while in1.value < in2.value : transfer item from in1 to output 
    while in2.value < in1.value : transfer item from in2 to output 

    if in1.value == in2.value : 
    transfer item from in1 to output 
    discard item from in2 

    while in1.value == value just transferred : disard item from in1 
    while in2.value == value just transferred : disard item from in2

現在討厭的 - 這個循環假設表是無限的。你如何處理空列表？這很煩瑣，除非你能保留一個sentinel value，該值大於列表中可能出現的任何合法值。

如果你不能保留一個哨兵，你可以僞造這個效果 - 編寫一個比較函數，在比較值之前檢查每個隊列中是否有下一個項目，並將「隊列窮盡」看作是哨兵值。

這給了...

loop forever 
    while in1.value < in2.value : discard item from in1 
    while in2.value < in1.value : discard item from in2 

    if in1 exhausted, break out of loop 
    if in2 exhausted, break out of loop 

    if in1.value == in2.value : 
    transfer item from in1 to output 
    discard item from in2 

    while in1.value == value just transferred : discard item from in1 
    while in2.value == value just transferred : discard item from in2

OOPS

這是一個工會。轉換爲十字路口是作爲讀者的練習。

編輯

確定 - 它現在是一個交集。只是拋棄不足的項目，而不是將它們添加到輸出中。還修復了一個錯字。

注意 - 我的解釋是交集的輸出應該是一個集合，意思是沒有重複。這容忍在輸入中的重複，但輸出是免費的。

來源

2010-01-31 11:39:50 Steve314

下面的解決方案如何，它是O（n + m），並採取指向頭節點的虛擬節點。 Head節點在這裏是一個類級別的變量，所以即使L1指向當前，Head總是擁有完整的列表。

我已編譯和測試，運行良好像L1簡單輸入：1-> 5> 6> 7> 8> 10和L2：2> 4> 6> 8時，輸出爲6> 8

任何有關如何去未排序列表的想法？我不能認爲一個爲O（n）溶液

public Node ReturnIntersection(Node Head, Node L2) { if ((Head == null) || (L2 == null)) return null;

 Node temp = null; 
     Node L1 = Head; 


     while (L1.next != null && L2.next != null) 
     { 
      if (L1.data == L2.data) 
      { 
       L1 = L1.next; 
       L2 = L2.next; 
      } 

      else if (L1.data < L2.data) 
      { 
       temp = L1.next; 
       L1.data = temp.data; 
       L1.next = temp.next; 

      } 

      else if (L1.data > L2.data) 
      { 
       L2 = L2.next; 

      } 

     } 

     if (L1 != null) 
     { 
      while (L1.next != null) 
      { 
       L1.next = null; 

      } 
     } 
     return Head; 


    }

來源

2011-03-24 21:03:58 RashMans

的由於它們是單鏈表如果兩個鏈表相交他們會形成Y形狀與一個臂長於或等於另一個。令l1爲L1列表的長度，l2爲L2列表的長度。

假設l1> l2。從點（l1-l2）開始匹配列表L1的指針，並從它的開始匹配列表L2，並指向同一節點，該節點將作爲匹配點。

如果l2大於l1，則採用其他方式。

來源

2011-08-07 10:08:07 john

兩個鏈接列表的交集

回答

相關問題