c++链表实现集合的交并差

在 C++ 中，链表可以用于实现集合数据结构，如栈、队列等，但它们通常不是最高效的选择来实现集合的交、并、差操作，因为链表查找元素的时间复杂度较高（O(n)）。对于集合的这些操作，哈希表（如 `std::unordered_set` 或 `std::set`）通常更为合适，因为其查找效率接近 O(1)。

然而，如果你仍然选择链表作为基础，你可以手动实现一些基本的操作，比如：

1. **交集** (Intersection): 创建两个新链表，遍历每个链表，将存在于两个链表中的节点添加到新的交集链表中。

void intersection(Node* list1, Node* list2, Node*& result) {
   Node* current = nullptr;
   for (Node* node1 = list1; node1 != nullptr; node1 = node1->next) {
       if (findInList(list2, node1->value)) {
           if (!current)
               result = node1;
           else {
               Node* newNode = new Node(node1->value);
               newNode->prev = current;
               current->next = newNode;
               current = newNode;
           }
       }
   }
}

其中 `findInList` 函数用来查找链表中是否存在某个值。

2. **并集** (Union): 遍历两个链表，并将所有节点添加到结果链表中。

3. **差集** (Difference): 对于删除操作，需要先创建一个新的链表，然后从第一个链表开始，如果节点不在第二个链表中，则将其添加到结果链表中。

注意，由于链表操作效率不高，这样的实现可能会导致性能问题，特别是当集合较大时。实际项目中，推荐使用内置的数据结构或库函数来处理这些问题。下面是使用 `std::list` 的示例：

std::list<int> intersect(const std::list<int>& list1, const std::list<int>& list2) {
   std::list<int> result;
   for (auto it1 = list1.begin(); it1 != list1.end(); ++it1) {
       if (std::find(list2.begin(), list2.end(), *it1) != list2.end()) {
           result.push_back(*it1);
       }
   }
   return result;
}

std::list<int> unionAll(std::list<int>& list1, const std::list<int>& list2) {
   return list1.size() > list2.size() ? list1 : list2;
}

std::list<int> difference(const std::list<int>& list1, const std::list<int>& list2) {
   std::list<int> result;
   for (auto it1 = list1.begin(); it1 != list1.end(); ++it1) {
       if (std::find(list2.begin(), list2.end(), *it1) == list2.end()) {
           result.push_back(*it1);
       }
   }
   return result;
}