C++实现合并两个排序的链表

前言

本文介绍使用C++实现合并两个排序的链表的攻略。在介绍具体操作之前，我们需要了解一下链表的基本概念和操作。

链表基本概念和操作

链表是一种常见的数据结构，用于存储一系列的元素。每个元素都包含一个存储数据的字段和一个（或多个）指向下一个元素的指针。

链表有以下几个基本操作：

1. 插入元素（在链表头或指定位置插入）
2. 删除元素（删除链表头或指定位置的元素）
3. 遍历链表
4. 查找元素

合并两个排序的链表

假设我们有两个已经排序好的链表A和B，我们需要将它们合并成一个新的排序好的链表C。

使用C++实现合并两个排序的链表，步骤如下：

1. 定义一个新的链表C，初始化为空。
2. 定义两个指针，分别指向链表A和B的头结点。
3. 比较指针所指向的元素的大小，将较小的元素插入到链表C的尾部，指针向后移动一位。
4. 重复以上步骤，直到其中一个链表为空。
5. 将另一个非空链表全部插入到新链表C的尾部。

示例说明

示例1

假设我们有两个已经排序好的链表A和B：

链表A：1 -> 3 -> 5 -> 7
链表B：2 -> 4 -> 6 -> 8

我们需要将它们合并成一个新的排序好的链表C。使用C++代码实现如下：

// 定义链表结构体，Node表示链表的一个节点
struct Node {
    int val;       // 存储数据的字段
    Node* next;    // 指向下一个元素的指针，为空时表示链表结尾
    Node(int x) : val(x), next(NULL) {}  // 构造函数，用于初始化节点
};

Node* mergeTwoSortedLists(Node* l1, Node* l2) {
    // 定义新链表C，并初始化为空
    Node* dummy = new Node(0);
    Node* cur = dummy;
    // 定义两个指针，分别指向链表A和B的头结点
    Node* p1 = l1;
    Node* p2 = l2;

    // 比较指针所指向的元素的大小，将较小的元素插入到链表C的尾部，指针向后移动一位
    while (p1 != NULL && p2 != NULL) {
        if (p1->val < p2->val) {
            cur->next = p1;
            p1 = p1->next;
        } else {
            cur->next = p2;
            p2 = p2->next;
        }
        cur = cur->next;
    }

    // 将另一个非空链表全部插入到新链表C的尾部
    if (p1 == NULL) {
        cur->next = p2;
    } else {
        cur->next = p1;
    }

    // 返回新链表C的头结点
    return dummy->next;
}

最终合并得到新的链表C：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8。

示例2

假设我们有两个已经排序好的链表A和B：

链表A：1 -> 2 -> 3 -> 4
链表B：5 -> 6 -> 7 -> 8

我们需要将它们合并成一个新的排序好的链表C。使用C++代码实现如下：

// 定义链表结构体，Node表示链表的一个节点
struct Node {
    int val;       // 存储数据的字段
    Node* next;    // 指向下一个元素的指针，为空时表示链表结尾
    Node(int x) : val(x), next(NULL) {}  // 构造函数，用于初始化节点
};

Node* mergeTwoSortedLists(Node* l1, Node* l2) {
    // 定义新链表C，并初始化为空
    Node* dummy = new Node(0);
    Node* cur = dummy;
    // 定义两个指针，分别指向链表A和B的头结点
    Node* p1 = l1;
    Node* p2 = l2;

    // 比较指针所指向的元素的大小，将较小的元素插入到链表C的尾部，指针向后移动一位
    while (p1 != NULL && p2 != NULL) {
        if (p1->val < p2->val) {
            cur->next = p1;
            p1 = p1->next;
        } else {
            cur->next = p2;
            p2 = p2->next;
        }
        cur = cur->next;
    }

    // 将另一个非空链表全部插入到新链表C的尾部
    if (p1 == NULL) {
        cur->next = p2;
    } else {
        cur->next = p1;
    }

    // 返回新链表C的头结点
    return dummy->next;
}

最终合并得到新的链表C：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8。

结论

使用C++实现合并两个排序的链表比较简单，只需要定义一个新的空链表C和两个指针，然后比较指针所指向元素的大小，将较小的元素插入到链表C的尾部即可。最后将另一个非空链表全部插入到链表C的尾部，返回链表C的头节点即可。