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

#include <iostream>
using namespace std;

template <class T>
class Node{
public:
T data;
Node<T>* next;
Node():next(nullptr){}
Node(T x):data(x),next(nullptr){}
};

template <class T>
class List{
public:
List():head(nullptr),tail(nullptr){}
~List(){clear();}
void clear();
void insert(T x);
void merge(List<T>& l1, List<T>& l2);
void display();

private:
Node<T>* head;
Node<T>* tail;
};

template <class T>
void List<T>::clear(){
Node<T>* p;
while(head){
p = head->next;
delete head;
head = p;
}
tail = nullptr;
}

template <class T>
void List<T>::insert(T x){
if(!head){
head = tail = new Node<T>(x);
}else{
tail->next = new Node<T>(x);
tail = tail->next;
}
}

template <class T>
void List<T>::merge(List<T>& l1, List<T>& l2){
Node<T>* p1 = l1.head;
Node<T>* p2 = l2.head;
while(p1 && p2){
if(p1->data < p2->data){
insert(p1->data);
p1 = p1->next;
}else if(p1->data > p2->data){
insert(p2->data);
p2 = p2->next;
}else{
insert(p1->data);
p1 = p1->next;
p2 = p2->next;
}
}
while(p1){
insert(p1->data);
p1 = p1->next;
}
while(p2){
insert(p2->data);
p2 = p2->next;
}
}

template <class T>
void List<T>::display(){
Node<T>* p = head;
while(p){
cout << p->data << " ";
p = p->next;
}
cout << endl;
}

class Student{
public:
Student(){}
Student(string n, int a):name(n),age(a){}
bool operator <(Student& s){return age < s.age;}
bool operator >(Student& s){return age > s.age;}
bool operator ==(Student& s){return age == s.age;}
friend ostream& operator <<(ostream& out, Student& s){out << s.name << "(" << s.age << ")"; return out;}

private:
string name;
int age;
};

int main(){
List<Student> l1, l2, l3;
l1.insert(Student("Tom", 18));
l1.insert(Student("Jack", 20));
l1.insert(Student("Mary", 19));
l1.display(); // Tom(18) Jack(20) Mary(19)
l2.insert(Student("Lucy", 22));
l2.insert(Student("Tom", 18));
l2.insert(Student("Mike", 21));
l2.display(); // Lucy(22) Tom(18) Mike(21)
l3.merge(l1, l2);
l3.display(); // Tom(18) Jack(20) Mary(19) Mike(21) Lucy(22)
return 0;
}