如何用C++语言合并两个链表

可以使用以下代码来合并两个链表：

#include <stdio.h>
#include <stdlib.h>

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

void push(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}

struct Node* mergeLists(struct Node* head1, struct Node* head2) {
    struct Node* mergedList = NULL;

    if (head1 == NULL) {
        return head2;
    }
    else if (head2 == NULL) {
        return head1;
    }

    if (head1->data <= head2->data) {
        mergedList = head1;
        mergedList->next = mergeLists(head1->next, head2);
    }
    else {
        mergedList = head2;
        mergedList->next = mergeLists(head1, head2->next);
    }

    return mergedList;
}

int main() {
    struct Node* head1 = NULL;
    struct Node* head2 = NULL;

    push(&head1, 7);
    push(&head1, 5);
    push(&head1, 3);
    push(&head1, 1);

    push(&head2, 8);
    push(&head2, 6);
    push(&head2, 4);
    push(&head2, 2);

    printf("List 1: ");
    printList(head1);
    printf("\nList 2: ");
    printList(head2);

    struct Node* mergedList = mergeLists(head1, head2);

    printf("\nMerged List: ");
    printList(mergedList);

    return 0;
}

这个程序使用递归的方式合并两个链表。首先，我们定义了一个 `Node` 结构体来表示链表中的每个节点。然后，我们定义了一个 `push` 函数来向链表中添加新的节点。接下来，我们定义了一个 `printList` 函数来打印链表中的所有节点。最后，我们定义了一个 `mergeLists` 函数来合并两个链表。

在 `mergeLists` 函数中，我们首先检查两个链表是否为空。如果其中一个链表为空，我们直接返回另一个链表。否则，我们比较两个链表的头节点，将较小的节点作为合并后链表的头节点，并递归地将剩余的节点合并到新链表中。

在 `main` 函数中，我们创建了两个链表，并将它们合并到一个新的链表中。最后，我们打印了原始链表和合并后的链表。