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

以下是一个可能的实现：

#include <iostream>

template<typename T>
class Node {
public:
    T data;
    Node<T>* next;

    Node() {
        next = nullptr;
    }

    Node(T value) {
        data = value;
        next = nullptr;
    }
};

template<typename T>
class LinkedList {
public:
    Node<T>* head;

    LinkedList() {
        head = new Node<T>();
    }

    ~LinkedList() {
        Node<T>* p = head;
        while (p != nullptr) {
            Node<T>* q = p->next;
            delete p;
            p = q;
        }
    }

    void insert(T value) {
        Node<T>* p = head;
        while (p->next != nullptr && p->next->data < value) {
            p = p->next;
        }
        Node<T>* q = new Node<T>(value);
        q->next = p->next;
        p->next = q;
    }
};

template<typename T>
LinkedList<T>* mergeLinkedList(LinkedList<T>* list1, LinkedList<T>* list2) {
    LinkedList<T>* result = new LinkedList<T>();
    Node<T>* p = list1->head->next;
    Node<T>* q = list2->head->next;
    while (p != nullptr && q != nullptr) {
        if (p->data < q->data) {
            result->insert(p->data);
            p = p->next;
        } else if (p->data > q->data) {
            result->insert(q->data);
            q = q->next;
        } else {
            result->insert(p->data);
            p = p->next;
            q = q->next;
        }
    }
    while (p != nullptr) {
        result->insert(p->data);
        p = p->next;
    }
    while (q != nullptr) {
        result->insert(q->data);
        q = q->next;
    }
    return result;
}

int main() {
    LinkedList<int>* list1 = new LinkedList<int>();
    list1->insert(1);
    list1->insert(3);
    list1->insert(5);
    LinkedList<int>* list2 = new LinkedList<int>();
    list2->insert(2);
    list2->insert(4);
    list2->insert(6);
    LinkedList<int>* result = mergeLinkedList(list1, list2);
    Node<int>* p = result->head->next;
    while (p != nullptr) {
        std::cout << p->data << " ";
        p = p->next;
    }
    std::cout << std::endl;
    delete list1;
    delete list2;
    delete result;
    return 0;
}

该实现中，我们定义了一个 `Node` 类来表示链表中的节点，每个节点包含一个 `data` 域和一个指向下一个节点的指针 `next`。然后我们定义了一个 `LinkedList` 类来表示链表本身，每个链表包含一个头节点 `head`，头节点不包含任何数据，只是一个辅助节点。我们给 `LinkedList` 类定义了一个 `insert` 函数来向链表中插入元素，该函数会按照关键字顺序将元素插入到链表中。

然后我们定义了一个 `mergeLinkedList` 函数，该函数接受两个链表作为参数，返回一个新的链表，该链表包含两个输入链表中所有不同的元素，且按照关键字顺序排列。该函数通过遍历两个输入链表，比较元素的关键字，将较小的元素插入到新的链表中。如果两个元素的关键字相同，则只插入其中一个。最后，如果有一个输入链表还有剩余元素，将剩余元素插入到新的链表中。

最后，在 `main` 函数中，我们创建了两个有序链表，然后调用 `mergeLinkedList` 函数将它们合并成一个新的有序链表，并打印出结果。最后，我们释放了所有动态分配的内存。