用单链表求两个集合的并集

假设我们有两个单链表A和B，它们分别表示两个集合。为了求它们的并集，我们可以遍历链表A和B，并将链表B中不在链表A中的元素插入到链表A的末尾。具体步骤如下：

1. 遍历链表A，对于每一个节点，检查该节点对应的元素是否在链表B中出现过，如果出现过，则跳过该节点；如果没有出现过，则将该节点插入到链表B的末尾。

2. 返回链表A，此时链表A中包含了两个集合的并集。

下面是C++代码实现：

#include <iostream>
#include <unordered_set>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    if (!headA || !headB) {
        return NULL;
    }
    // 将链表A中的元素插入到哈希表中
    unordered_set<int> hashset;
    ListNode* p = headA;
    while (p) {
        hashset.insert(p->val);
        p = p->next;
    }
    // 遍历链表B，将不在哈希表中的元素插入到链表A的末尾
    p = headB;
    while (p) {
        if (hashset.find(p->val) == hashset.end()) {
            ListNode* node = new ListNode(p->val);
            node->next = headA;
            headA = node;
        }
        p = p->next;
    }
    return headA;
}

int main() {
    // 构造两个集合的单链表表示
    ListNode* headA = new ListNode(1);
    headA->next = new ListNode(2);
    headA->next->next = new ListNode(3);
    headA->next->next->next = new ListNode(4);
    headA->next->next->next->next = new ListNode(5);
    ListNode* headB = new ListNode(4);
    headB->next = new ListNode(5);
    headB->next->next = new ListNode(6);
    headB->next->next->next = new ListNode(7);
    // 求两个集合的并集
    ListNode* head = getIntersectionNode(headA, headB);
    // 输出结果
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
    return 0;
}

注意，上述代码中的getIntersectionNode函数实际上是求两个集合的交集，如果将其改为并集，只需要将第二个while循环中的if条件语句改为hashset.find(p->val) != hashset.end()即可。