創建LinkedListC中的鏈接列表A和B共有的元素C++

正如問題的名稱所示。我需要採取2個鏈表，並創建第三個列表中的前兩個鏈接列表通用的元素。創建LinkedListC中的鏈接列表A和B共有的元素C++

這裏是我寫

void computeC(DLL<int> &a, DLL<int> &b, DLL<int> &c) 
{ 
    Node<int> *hunterA, *hunterB; 
    hunterA = a.getHead(); 
    hunterB = b.getHead(); 


    while (hunterA != NULL) 
    { 
     while (hunterB != NULL) 
     { 
      int aData = hunterA->data, bData = hunterB->data; 

      if (aData == bData) 
      { 
        int temp = bData; 
       c.progAppend2(temp); 
      } 
      else 
      { 
       hunterB = hunterB->next; 
      } 
     } 
     hunterA = hunterA->next; 
    } 
    c.output(); 
}

這裏是我的雙向鏈表類

template <class Type> 
void DLL<Type>::progAppend2(Type data) 
{ 
    Node<Type> *newNode = new Node<Type>; 
    newNode->data = data; 

    if (head == NULL) 
    { 
     head = newNode; 
     tail = newNode; 
     size++; 
    } 

    else 
    { 
     tail->next = newNode; 
     newNode->prev = tail; 
     tail = tail->next; 
     size++; 
    } 
}

的progAppend2（）函數的函數，這裏是主要的（）

int main (void) 
{ 
    int a[9] = {3,7,10,15,16,9,22,17,32}; 
    int b[9] = {16,2,9,13,37,8,10,1,28}; 
    DLL<int> listA, listB, listC, listD; 
    for (int i = 0; i < 9; i++) 
    { 
     listA.progAppend2(a[i]); 
     listB.progAppend2(b[i]); 
    } 
    computeC(listA,listB,listC); 
    listC.output(); 

    return 0; 
}

我遇到的問題是由於某種原因，ListC沒有被填充任何東西，只是輸出和空的lis當我調用output（）;

我認爲問題在於computeC函數。 outer while循環應該設置hunterA指向ListA中的一個元素，然後內部循環應該將listB的每個元素與hunterA指向的元素進行比較。如果找到匹配項，那麼該元素將被複制到ListC中。在這種情況下，我認爲它應該工作。我真的很感激任何幫助。

來源

2013-05-06 mooms419

的可能重複[鏈表路口（http://stackoverflow.com/questions/8919442/linked-list-intersection） – 2013-05-08 20:28:53

每次檢查A中的新節點時，都需要再次查看B中的所有節點。例如，如果A中的第一個節點不匹配B中的任何元素（就像在輸入中一樣），則指針將移動到B的末尾。因此，在通過A移動的while循環中，將b指針重置爲B列表的開始。

注意：如果a和b中的節點匹配，您也會進入無限循環，因爲您無法在if-then語句中移動b指針。

來源

2013-05-06 22:52:14

我認爲@ A.E.Drew有適合您的建議。（長度（A）*長度（B）），更好的解決方案是O（長度（A）+長度（B））。我只想補充一點，您的解決方案的時間複雜度爲O（長度（A）*長度（B））。您可以散列所有A列表節點，然後迭代B列表以查找是否有任何B節點在A列表中。

希望這可以幫助:)

來源

2013-05-07 06:16:10 hongtao

創建LinkedListC中的鏈接列表A和B共有的元素C++

回答

相關問題