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

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

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

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

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

这样，它总共可以在O（n）时间内完成。

Answer 2

如果链表中的值允许，您可以使用第一个链接的值创建直方图，然后遍历第二个列表，并在此过程中递减直方图条目。如果最后直方图只包含零，那么它们是相同的。

因此，例如，如果 list1 包含 {1， 3， 4， 2， 4}，则直方图将为（从零开始）[0， 1， 1， 1， 2]。

然后，如果 list2 包含 {1， 3， 2， 4}，则递减后直方图将为 [0， 0， 0， 0， 1]。

运行时间为 O（m + n）

Answer 3

这个解决方案需要相同的时间复杂性，但仍然好一点！

{
 while(node1->next != NULL)
 {
    if(!contains(node2, node1->value)){
        return false;
    }
    node1 = node1->next;
 }
 return true;
}

Answer 4

您可以将数字打印成一个字符串，然后对字符串进行排序，以便所有内容都按正确的顺序排列

编辑：这只是一个建议，你的其他方式更好

Answer 5

这是绝对有效的递归解决方案....

int CompareLists(Node *headA, Node* headB)
{
if (headA == NULL && headB == NULL)     
{  return 1;  }
if (headA == NULL && headB != NULL)  
{  return 0;  }
if (headB != NULL && headB == NULL)  
{  return 0;  }
if (headA->data != headB->data)
{  return 0;  }
return CompareLists(headA->next, headB->next);  
}