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

#include <iostream>
using namespace std;

template <class T>
class Node {
public:
T data;
Node* next;
Node() {
next = NULL;
}
Node(T d, Node* n = NULL) {
data = d;
next = n;
}
};

template <class T>
class List {
public:
List() {
head = new Node<T>();
}
void insert(T d) {
Node<T>* p = head;
while (p->next != NULL && p->next->data < d) {
p = p->next;
}
if (p->next == NULL || p->next->data != d) {
p->next = new Node<T>(d, p->next);
}
}
void print() {
Node<T>* p = head->next;
while (p != NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
friend List<T> merge(List<T>& list1, List<T>& list2) {
List<T> newList;
Node<T>* p1 = list1.head->next;
Node<T>* p2 = list2.head->next;
while (p1 != NULL && p2 != NULL) {
if (p1->data < p2->data) {
newList.insert(p1->data);
p1 = p1->next;
}
else if (p1->data > p2->data) {
newList.insert(p2->data);
p2 = p2->next;
}
else {
newList.insert(p1->data);
p1 = p1->next;
p2 = p2->next;
}
}
while (p1 != NULL) {
newList.insert(p1->data);
p1 = p1->next;
}
while (p2 != NULL) {
newList.insert(p2->data);
p2 = p2->next;
}
return newList;
}
private:
Node<T>* head;
};

class Student {
public:
Student(int i, string n) {
id = i;
name = n;
}
bool operator<(const Student& s) const {
return id < s.id;
}
bool operator==(const Student& s) const {
return id == s.id;
}
friend ostream& operator<<(ostream& out, const Student& s) {
out << s.id << ":" << s.name;
return out;
}
private:
int id;
string name;
};

int main() {
List<int> list1;
list1.insert(1);
list1.insert(3);
list1.insert(5);
List<int> list2;
list2.insert(2);
list2.insert(4);
list2.insert(6);
List<int> newList = List<int>::merge(list1, list2);
newList.print();

List<Student> list3;
list3.insert(Student(3, "Tom"));
list3.insert(Student(1, "Jack"));
list3.insert(Student(2, "Mike"));
List<Student> list4;
list4.insert(Student(4, "Mary"));
list4.insert(Student(2, "Mike"));
list4.insert(Student(5, "Lucy"));
List<Student> newList2 = List<Student>::merge(list3, list4);
newList2.print();
return 0;
}