C:链表中的搜索功能

Question

我有两个链表。

typedef struct node
{
   char value[256];
   struct node *next;
} Node_t;
    typedef struct node1
    {
       char value1[256];
       int count;
       struct node1 *next;
    } Node1_t;

两个链表都有数据，我想比较两个链表之间的数据，哪些数据是常见的，有没有办法在两个链表中找到相似的数据？

谢谢。

Answer 1

如果两个列表都已排序，则可以使用以下算法（伪代码，运行时复杂度O(n+m)）：

INPUT: list1, list2 (first nodes of the lists you want to compare, sorted!)
while list1 != null AND list2 != null
    if list1->value < list2->value
        list1->value = list1->next
    elseif
        list2->value < list1->value
          list2->value = list2->next
    else
        list3->appendValue(list1->value)
        list1->next

如果其中一个列表没有排序，则必须将第一个列表中的每个元素与第二个列表中每个元素进行比较（运行时复杂性O(n*m)）：

INPUT: list1, list2 (first nodes of the lists you want to compare)
while list1 != null
    list2temp = list2
    while list2temp != null
        if list1->value == list2temp->value
            list3->appendValue(list1->value)
        list2temp = list2temp->next
    list1 = list1->next

通常最好先对列表进行排序，然后使用第一种方法，这将导致O(n log n + m log m)的运行时复杂性。在这两种情况下，list3都将包含两个列表的公共元素。

Answer 2

list = head;
while (list) {
  list1 = head1;
  while (list1) {
    if (yourcompare(list->value, list1->value) == 0) {
      // do something with common data
      // if only possible case: then break;
    }
    list1 = list1->next;
  }
  list = list->next;
}

如果list1中曾经匹配过的值不应该再次匹配，则可以添加类似"shortupdated"的记账数据。因此，您需要内部while中的"if（！list1->updated）｛…；list1->updated=TRUE；｝"。