c++ - 检查两个单链表是否包含相同的数据

Question

我们必须检查两个给定的链表是否包含相同的数据。在这种情况下，顺序并不重要，这意味着 {1,3,2} 和 {2,1,3} 是相同的。我认为我们应该引入一个新变量 counter=0 并执行以下过程:

while(node1->next!=NULL)
{
    int value=node1->value;
    if(contains(node2,value)){
        counter++;
    }

    node1=node1->next;

    if(counter== number of elements in node 1) 
        return true; 
    else return false;
}

另一种方法是对两个列表进行排序并逐个节点进行比较。哪一个是最佳的？在第一种情况下，需要 O(n^2) 次操作，而在第二种情况下，需要 Nlog(N)+O(N)(如果我们使用合并排序)。我的想法正确吗？或者还有其他最佳方法吗？

Answer 1

在您发布的两种方法中，第二种更好。但我建议你散列。

首先对第一个链表进行哈希处理。

在散列时检查第二个列表。

这样，总共可以在 O(n) 时间内完成。