链表是一种常用的数据结构，它由一系列的节点组成，每个节点包含一个数据域和一个指向下一个节点的指针。链表的优点是可以动态地增加或删除节点，不需要连续的内存空间。链表的缺点是访问节点的时间复杂度是O(n)，而不是像数组那样是O(1)。
有序链表是一种特殊的链表，它的节点按照某种规则（如升序或降序）排列。有序链表的优点是可以方便地进行查找、插入和删除操作，而且保持链表的有序性。有序链表的缺点是在插入或删除节点时，需要遍历链表，找到合适的位置，这会增加时间开销。
有时候，我们需要把两个有序链表合并成一个有序链表，这是一个常见的编程问题。例如，如果我们有两个升序的链表，我们希望得到一个包含所有节点的升序链表。这个问题的一个应用场景是，如果我们有两个分别存储了不同部分的有序数据的链表，我们想要把它们合并成一个完整的有序数据的链表。
在本文中，我们将介绍如何用C++实现两个有序链表的合并，并给出一个示例代码。我们假设两个链表都是升序的，如果是降序的，只需要稍微修改一下代码即可。
定义链表节点和链表类
首先，我们需要定义链表节点和链表类。链表节点是一个结构体，它包含一个整型的数据域和一个指向下一个节点的指针。链表类是一个类，它包含一个指向头节点的指针和一个指向尾节点的指针。链表类还提供了一些基本的操作，如构造函数、析构函数、插入节点、删除节点、打印链表等。这里我们只给出部分代码，完整的代码可以在附录中找到。
// 链表节点结构体
int val; // 数据域
ListNode* next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(nullptr) {} // 构造函数
// 链表类
ListNode* head; // 头节点指针
ListNode* tail; // 尾节点指针
LinkedList() : head(nullptr), tail(nullptr) {} // 构造函数
~LinkedList(); // 析构函数
void insert(int x); // 插入节点
void remove(int x); // 删除节点
void print(); // 打印链表
ListNode* getHead() { return head; } // 获取头节点指针
实现两个有序链表的合并
接下来，我们需要实现两个有序链表的合并。我们可以使用一个双指针的方法，同时遍历两个链表，比较它们的节点的值，把较小的节点插入到新的链表中，然后移动对应的指针，直到其中一个链表为空，再把另一个链表的剩余部分接到新的链表后面。这个方法的时间复杂度是O(m+n)，其中m和n分别是两个链表的长度，空间复杂度是O(1)，因为我们只需要额外的几个指针。
我们定义一个名为mergeTwoSortedLists的函数，它接受两个链表的头节点指针作为参数，返回合并后的链表的头节点指针。函数的实现如下：
// 合并两个有序链表
// 如果其中一个链表为空，直接返回另一个链表
// 定义一个哑节点，作为新链表的头节点的前驱
// 定义一个指针，指向新链表的当前节点
// 定义两个指针，分别指向两个链表的当前节点
// 当两个链表都不为空时，循环比较它们的节点的值，把较小的节点插入到新链表中
// 如果p1的节点的值小于等于p2的节点的值，把p1的节点接到新链表后面，然后移动p1
// 否则，把p2的节点接到新链表后面，然后移动p2
// 如果p1不为空，把p1的剩余部分接到新链表后面
// 如果p2不为空，把p2的剩余部分接到新链表后面
// 返回新链表的头节点