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

// C++ 代码
#include <iostream>
using namespace std;

// 定义链表节点类
class Node {
public:
int data;
Node* next;
Node(int d) : data(d), next(nullptr) {}
};

// 定义链表类
class List {
private:
Node* head;
public:
List() : head(nullptr) {}
void insert(int d) {
Node* new_node = new Node(d);
if (!head) {
head = new_node;
} else {
Node* curr = head;
while (curr->next) {
curr = curr->next;
}
curr->next = new_node;
}
}
friend List merge(List& l1, List& l2) {
List res;
Node* p1 = l1.head;
Node* p2 = l2.head;
while (p1 && p2) {
if (p1->data < p2->data) {
res.insert(p1->data);
p1 = p1->next;
} else if (p1->data > p2->data) {
res.insert(p2->data);
p2 = p2->next;
} else {
res.insert(p1->data);
p1 = p1->next;
p2 = p2->next;
}
}
while (p1) {
res.insert(p1->data);
p1 = p1->next;
}
while (p2) {
res.insert(p2->data);
p2 = p2->next;
}
return res;
}
void print() {
Node* curr = head;
while (curr) {
cout << curr->data << " ";
curr = curr->next;
}
cout << endl;
}
};

int main() {
List l1, l2;
l1.insert(1);
l1.insert(3);
l1.insert(5);
l2.insert(2);
l2.insert(4);
l2.insert(6);
List l3 = List::merge(l1, l2);
l3.print();
return 0;
}