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

#include <iostream>
using namespace std;

template<class T>
class Node{
public:
    T data; //数据域
    Node<T> *next; //指针域
    Node(const T &x, Node<T> *n = NULL){ //构造函数
        data = x;
        next = n;
    }
    Node(){next = NULL;} //构造函数
    ~Node(){} //析构函数
};

template<class T>
class List{
public:
    List(){head = new Node<T>; head->next = NULL;} //构造函数
    ~List(){makeEmpty();} //析构函数
    void makeEmpty(); //置空函数
    Node<T> *getHead() const{return head;}
    int Length() const; //求长度函数
    Node<T> *Search(const T &x) const; //查找函数
    Node<T> *Locate(int i) const; //定位函数
    bool getData(int i, T &x) const; //取数据函数
    void setData(int i, const T &x); //设置数据函数
    bool Insert(int i, const T &x); //插入函数
    bool Remove(int i, T &x); //删除函数
    bool IsEmpty() const{return head->next == NULL;} //判断是否为空
    bool IsFull() const{return false;} //判断是否为满
    void Sort(); //排序函数
    void Reverse(); //逆置函数
    void Merge(List<T> &list); //合并函数
    void Print() const; //输出函数
    friend void TestList(); //测试函数
private:
    Node<T> *head; //头指针
};

template<class T>
void List<T>::makeEmpty(){ //置空函数
    Node<T> *p = head->next, *q;
    head->next = NULL;
    while(p != NULL){
        q = p->next;
        delete p;
        p = q;
    }
}

template<class T>
int List<T>::Length() const{ //求长度函数
    Node<T> *p = head->next;
    int len = 0;
    while(p != NULL){
        len++;
        p = p->next;
    }
    return len;
}

template<class T>
Node<T> *List<T>::Search(const T &x) const{ //查找函数
    Node<T> *p = head->next;
    while(p != NULL && p->data != x)
        p = p->next;
    return p;
}

template<class T>
Node<T> *List<T>::Locate(int i) const{ //定位函数
    if(i < 0) return NULL;
    Node<T> *p = head;
    int j = -1;
    while(p != NULL && j < i){
        j++;
        p = p->next;
    }
    return p;
}

template<class T>
bool List<T>::getData(int i, T &x) const{ //取数据函数
    if(i < 0) return false;
    Node<T> *p = Locate(i);
    if(p == NULL) return false;
    else{
        x = p->data;
        return true;
    }
}

template<class T>
void List<T>::setData(int i, const T &x){ //设置数据函数
    if(i < 0) return;
    Node<T> *p = Locate(i);
    if(p == NULL) return;
    else p->data = x;
}

template<class T>
bool List<T>::Insert(int i, const T &x){ //插入函数
    Node<T> *p = Locate(i - 1);
    if(p == NULL) return false;
    else{
        Node<T> *q = new Node<T>(x, p->next);
        p->next = q;
        return true;
    }
}

template<class T>
bool List<T>::Remove(int i, T &x){ //删除函数
    Node<T> *p = Locate(i - 1);
    if(p == NULL || p->next == NULL) return false;
    else{
        Node<T> *q = p->next;
        x = q->data;
        p->next = q->next;
        delete q;
        return true;
    }
}

template<class T>
void List<T>::Sort(){ //排序函数（冒泡排序）
    Node<T> *p = head->next, *q;
    T temp;
    while(p != NULL){
        q = p->next;
        while(q != NULL){
            if(p->data > q->data){
                temp = p->data;
                p->data = q->data;
                q->data = temp;
            }
            q = q->next;
        }
        p = p->next;
    }
}

template<class T>
void List<T>::Reverse(){ //逆置函数
    Node<T> *p = head->next, *q;
    head->next = NULL;
    while(p != NULL){
        q = p->next;
        p->next = head->next;
        head->next = p;
        p = q;
    }
}

template<class T>
void List<T>::Merge(List<T> &list){ //合并函数
    Node<T> *a = head->next, *b = list.getHead()->next, *c = head;
    while(a != NULL && b != NULL){
        if(a->data < b->data){
            c->next = a;
            a = a->next;
            c = c->next;
        }
        else if(a->data > b->data){
            c->next = b;
            b = b->next;
            c = c->next;
        }
        else{
            c->next = a;
            a = a->next;
            b = b->next;
            c = c->next;
        }
    }
    if(a != NULL)
        c->next = a;
    else if(b != NULL)
        c->next = b;
}

template<class T>
void List<T>::Print() const{ //输出函数
    Node<T> *p = head->next;
    while(p != NULL){
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

void TestList(){ //测试函数
    List<int> L1, L2;
    int a[5] = {1, 3, 5, 7, 9}, b[5] = {2, 4, 6, 8, 10};
    for(int i = 0; i < 5; i++)
        L1.Insert(i, a[i]);
    for(int i = 0; i < 5; i++)
        L2.Insert(i, b[i]);
    cout << "L1: ";
    L1.Print();
    cout << "L2: ";
    L2.Print();
    L1.Merge(L2);
    cout << "L1 after merge: ";
    L1.Print();
}

int main(){
    TestList();
    return 0;
}