用C++，设有两条有序链表（即 data 域元素的关键字由前往后不断增大），试设计算法，将这两 条链表合并为一条新的有序链表，原链表不变。两条链表中 data 域关键字相同的元素只选 取一个存储到新的有序链表中，不同的元素都存储到新的有序链表中。 要求： ➢ 直接编写链表的友元函数完成该功能。 ➢ 链表的 data 域可存储用户自定义类对象。 ➢ 编写测试 main()函数测试线性表的正确性

#include <iostream>
using namespace std;

class Element {
public:
int key; //关键字
Element* next; //指向下一个元素的指针

Element(int k = 0, Element* n = nullptr) : key(k), next(n) {}
};

class List {
private:
Element* head; //头指针
public:
List() : head(nullptr) {}
~List() {
Element* p = head;
while (p != nullptr) {
Element* q = p;
p = p->next;
delete q;
}
}
void insert(int k) { //按关键字插入元素
if (head == nullptr) {
head = new Element(k, nullptr);
return;
}
if (k < head->key) {
head = new Element(k, head);
return;
}
Element* p = head;
while (p->next != nullptr && k > p->next->key) {
p = p->next;
}
p->next = new Element(k, p->next);
}

friend List merge(const List& list1, const List& list2) { //合并两个有序链表
List list;
Element* p = list1.head;
Element* q = list2.head;
while (p != nullptr && q != nullptr) {
if (p->key < q->key) {
list.insert(p->key);
p = p->next;
}
else if (p->key > q->key) {
list.insert(q->key);
q = q->next;
}
else {
list.insert(p->key);
p = p->next;
q = q->next;
}
}
while (p != nullptr) {
list.insert(p->key);
p = p->next;
}
while (q != nullptr) {
list.insert(q->key);
q = q->next;
}
return list;
}

void print() { //输出链表
Element* p = head;
while (p != nullptr) {
cout << p->key << " ";
p = p->next;
}
cout << endl;
}
};

int main() {
List list1, list2;
list1.insert(1);
list1.insert(3);
list1.insert(5);
list2.insert(2);
list2.insert(4);
list2.insert(5);
List list3 = merge(list1, list2);
list1.print();
list2.print();
list3.print();
return 0;
}