用c++中链表A和链表B的共同元素创建一个linkedListC

Question

顾名思义。我需要取两个链表，并仅从前两个链表共有的元素中创建第三个列表。

这是我写的函数

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();
}

下面是我的双链表类

中的progAppend2()函数

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++;
    }
}

，这里是main()

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没有被填充任何东西，只是输出和空列表，当我调用output();

我想问题出在computeC的功能上。外部while循环应该设置hunterA指向ListA中的一个元素，然后内部循环应该将listB中的每个元素与hunterA指向的元素进行比较。如果找到匹配项，则将该元素复制到ListC中。至少我是这么认为的。我将非常感谢您的帮助。

Answer 1

每次检查a中的一个新节点时，都需要再次查看B中的所有节点。例如，如果A中的第一个节点不匹配B中的任何元素(就像在你的输入中一样)，你的指针将移动到B的末尾。因此，在你的while循环遍历A时，将B指针重置为B列表的开始。

注意:如果a和b中的节点匹配，它看起来也会进入一个无限循环，因为你没有在if-then语句中断开或移动b指针。

Answer 2

我认为@A.E。Drew给了你一个正确的建议。

我只是想补充一下，你的解决方案的时间复杂度是O(长度(A)*长度(B))，更好的解决方案是O(长度(A)+长度(B))。你可以哈希所有的A-list节点，然后迭代B-list来查找是否有B-node在A-list中。

希望这对你有帮助