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

下面是一个示例代码：

#include <iostream>
using namespace std;
template<typename T>
class LinkedList {
friend LinkedList<T> merge(LinkedList<T>& list1, LinkedList<T>& list2) {
LinkedList<T> newList;
Node<T>* p1 = list1.head->next;
Node<T>* p2 = list2.head->next;
while(p1 != nullptr && p2 != nullptr) {
if(p1->data < p2->data) {
newList.insertTail(p1->data);
p1 = p1->next;
}
else if(p1->data > p2->data) {
newList.insertTail(p2->data);
p2 = p2->next;
}
else {
newList.insertTail(p1->data);
p1 = p1->next;
p2 = p2->next;
}
}
while(p1 != nullptr) {
newList.insertTail(p1->data);
p1 = p1->next;
}
while(p2 != nullptr) {
newList.insertTail(p2->data);
p2 = p2->next;
}
return newList;
}
public:
LinkedList():head(new Node<T>()) {}
~LinkedList() {
Node<T>* p = head;
while(p != nullptr) {
Node<T>* q = p->next;
delete p;
p = q;
}
}
void insertTail(T data) {
Node<T>* p = head;
while(p->next != nullptr) {
p = p->next;
}
p->next = new Node<T>(data);
}
void print() {
Node<T>* p = head->next;
while(p != nullptr) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
private:
template<typename U>
class Node {
public:
Node():next(nullptr) {}
Node(U data):data(data), next(nullptr) {}
U data;
Node* next;
};
Node<T>* head;
};
int main() {
LinkedList<int> list1, list2;
list1.insertTail(1);
list1.insertTail(2);
list1.insertTail(4);
list1.insertTail(6);
list2.insertTail(2);
list2.insertTail(3);
list2.insertTail(5);
list2.insertTail(6);
LinkedList<int> newList = merge(list1, list2);
newList.print(); // 1 2 3 4 5 6
return 0;
}