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

#include<iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int d, Node* n = NULL) :data(d), next(n) {};
};
class LinkList {
public:
LinkList() { head = new Node(0); }
void add(int d) {
Node* p = new Node(d);
p->next = head->next;
head->next = p;
}
void print() {
Node* p = head->next;
while (p) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
friend LinkList merge(LinkList& L1, LinkList& L2) {
LinkList L;
Node* p1 = L1.head->next;
Node* p2 = L2.head->next;
while (p1 && p2) {
if (p1->data < p2->data) {
L.add(p1->data);
p1 = p1->next;
}
else if (p1->data > p2->data) {
L.add(p2->data);
p2 = p2->next;
}
else {
L.add(p1->data);
p1 = p1->next;
p2 = p2->next;
}
}
while (p1) {
L.add(p1->data);
p1 = p1->next;
}
while (p2) {
L.add(p2->data);
p2 = p2->next;
}
return L;
}
private:
Node* head;
};
int main() {
LinkList L1, L2, L;
L1.add(5); L1.add(3); L1.add(1);
L2.add(6); L2.add(4); L2.add(2);
L1.print();
L2.print();
L = merge(L1, L2);
L.print();
return 0;
}