c plus plus 合并两个链表

假设有两个单向链表，我们可以按照以下步骤将它们合并：

1. 创建一个新的链表，作为合并后的链表。
2. 比较两个链表的首节点，将较小的节点添加到新链表中，并将指针指向下一个节点。
3. 重复步骤2，直到其中一个链表为空。
4. 将另一个链表剩余的节点添加到新链表的尾部。

下面是一个 C++ 的示例代码：

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

void append(Node** headRef, int newData) {
    Node* newNode = new Node;
    newNode->data = newData;
    newNode->next = nullptr;

    Node* last = *headRef;
    if (*headRef == nullptr) {
        *headRef = newNode;
        return;
    }

    while (last->next != nullptr) {
        last = last->next;
    }

    last->next = newNode;
}

void printList(Node* node) {
    while (node != nullptr) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}

Node* mergeLists(Node* list1, Node* list2) {
    Node* mergedList = nullptr;
    Node** tailRef = &mergedList;

    while (true) {
        if (list1 == nullptr) {
            *tailRef = list2;
            break;
        }
        else if (list2 == nullptr) {
            *tailRef = list1;
            break;
        }

        if (list1->data <= list2->data) {
            append(tailRef, list1->data);
            list1 = list1->next;
        }
        else {
            append(tailRef, list2->data);
            list2 = list2->next;
        }

        tailRef = &((*tailRef)->next);
    }

    return mergedList;
}

int main() {
    Node* list1 = nullptr;
    Node* list2 = nullptr;

    append(&list1, 1);
    append(&list1, 3);
    append(&list1, 5);

    append(&list2, 2);
    append(&list2, 4);
    append(&list2, 6);

    cout << "List 1: ";
    printList(list1);

    cout << "List 2: ";
    printList(list2);

    Node* mergedList = mergeLists(list1, list2);

    cout << "Merged list: ";
    printList(mergedList);

    return 0;
}

在这个示例代码中，我们首先定义了一个 `Node` 结构体，表示一个链表节点。然后定义了 `append` 函数用于在链表尾部添加节点，并定义了 `printList` 函数用于打印链表中的所有节点。

接下来定义了 `mergeLists` 函数，用于合并两个链表。该函数创建一个新的链表 `mergedList`，并使用指向指针的指针 `tailRef` 来跟踪新链表的尾节点。然后使用一个 `while` 循环来逐个比较两个链表中的节点，将较小的节点添加到新链表中。最后，将剩余的节点添加到新链表的尾部，并返回合并后的链表。

在 `main` 函数中，我们创建了两个链表，并将它们打印出来。然后调用 `mergeLists` 函数将它们合并，并将合并后的链表打印出来。