给定两个链表，求它们的交集以及并集。用于输出的list中的元素顺序可不予考虑。例子:输入下面两个链表: list1: 10->15->4->20 list2: 8->4->2->10输出链表: 交集list: 4->10 并集list: 2->8->20->4->15->10方法1 (简单方法)可以参考链表系列中的"链表操作 – 求两个链表的交集(intersection)以及并集(union)"方法2 (使用归并排序)可以参考链表系列中的"链表操作 – 求两个链表的交集(intersection)以及并集(union)"方法3 (使用哈希)calculateUnion (list1, list2)，求链表的并集的算法：将result list初始化为NULL，然后创建一个空的哈希表。依次遍历这两个链表，对于其中的每个元素，在哈希表中进行查找。如果元素不在哈希表中，，则将其插入到result list中，并插入到哈希表中。如果元素已经存在于哈希表中，则忽略它。calculateIntersection (list1, list2)，求链表的交集的算法：将result list初始化为NULL，然后创建一个空的哈希表。 遍历list1, 对于其中的每个元素，将其插入到哈希表中。然后遍历list2, 对于其中的每个元素，在哈希表中进行查找。如果元素已经存在于哈希表中，则插入到result list中。如果元素不在哈希表中，则忽略它。上面的这两个方法，即使list中存在重复的元素，也能处理。时间复杂度：方法3的时间复杂度取决于所使用的哈希方法，以及输入链表中的元素分布。在实际的情况中，方法3可能比前面的两种方法更好。代码如下：#include<iostream>#include<algorithm>#include<map>#include<list>void calculateUnion(const std::list<int>& list1, const std::list<int>& list2, std::list<int>& outputResult){std::map< int, bool> tmp;for (auto iter : list1){if (tmp.find(iter) == tmp.end())tmp.insert(std::make_pair(iter, true));}for (auto iter : list2){if (tmp.find(iter) == tmp.end())tmp.insert(std::make_pair(iter, true));}//convert map to listfor (auto iter : tmp){if (iter.second)outputResult.push_back(iter.first);}}void calculateIntersection(const std::list<int>& list1, const std::list<int>& list2, std::list<int>& outputResult){std::map< int, bool> tmp;for (auto iter : list1){tmp.insert(std::make_pair(iter, false));}for (auto iter : list2){if (tmp.find(iter) != tmp.end())outputResult.push_back(iter);}}int main(){//list1: 10->15->4->20//list2: 8->4->2->10std::list< int> list1, list2, result;list1.push_back(10);list1.push_back(15);list1.push_back(4);list1.push_back(20);list2.push_back(8);list2.push_back(4);list2.push_back(2);list2.push_back(10);calculateUnion(list1, list2, result);std::cout << "union result: \n";std::for_each(result.begin(), result.end(), [](const int& value){std::cout << value << " ";});result.clear();calculateIntersection(list1, list2, result);std::cout << "\nintersection result: \n";std::for_each(result.begin(), result.end(), [](const int& value){std::cout << value << " ";});std::cout << std::endl;return 0;}输出：union result:2 4 8 10 15 20intersection result:4 10
家!甜蜜的家!天下最美好的莫过於家
