2

我们必须检查两个给定的链表是否包含相同的数据。在这种情况下,顺序无关紧要,这意味着{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),(如果我们使用归并排序)。我的想法是对的吗?还是有其他最佳方法?

4

5 回答 5

2

在您发布的两种方法中,第二种更好。但我建议你这样做hashing

首先散列第一个链表。

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

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

于 2012-04-12T16:19:02.300 回答
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)

于 2012-04-12T16:19:40.920 回答
1

该解决方案需要相同的时间复杂度,但仍然要好一些!

{
 while(node1->next != NULL)
 {
    if(!contains(node2, node1->value)){
        return false;
    }
    node1 = node1->next;
 }
 return true;
}
于 2012-04-12T16:19:23.243 回答
0

您可以将数字打印到字符串中,然后对字符串进行排序,以便一切都按正确的顺序排列

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

于 2012-04-12T16:32:45.593 回答
0

这是肯定会起作用的递归解决方案....

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);  
}
于 2015-10-22T07:03:00.723 回答