带你了解如何用C++合并两个有序链表

下面是“带你了解如何用C++合并两个有序链表”的完整攻略。

1. 问题描述

我们有两个已经有序的链表l1和l2，请将它们合并成一个有序链表，并返回新链表的头节点。

例如，

输入：l1 = 1->2->4, l2 = 1->3->4
输出：1->1->2->3->4->4

2. 解决思路

在整个算法中，我们使用三个指针p1, p2,和p3。p1指向第一个链表的当前节点，p2指向第二个链表的当前节点，p3用于构建新链表。我们比较p1和p2所指向节点的值，如果p1的值比p2小，则将p1的节点插入到新链表中，并移动p1到下一节点；否则将p2的节点插入到新链表中，并移动p2。不断重复这个过程，直到其中一个链表为空，然后将不为空的链表拼接到新链表的尾部。最后返回新链表的头节点即可。

3. 详细代码

// 链表节点的结构体
struct ListNode {
    int val; // 节点值
    ListNode *next; // 指向下一个节点的指针
    ListNode(int x) : val(x), next(nullptr) {} // 构造函数
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 使用一个哨兵节点作为新链表的头节点
        ListNode *dummyHead = new ListNode(-1); 
        // 指向新链表的指针
        ListNode *p3 = dummyHead; 

        // 比较两个链表的当前节点大小，并将较小节点插入到新链表中
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                p3->next = l1;
                l1 = l1->next;
            } else {
                p3->next = l2;
                l2 = l2->next;
            }
            p3 = p3->next;
        }

        // 将不为空的链表拼接到新链表尾部
        p3->next = (l1 != nullptr) ? l1 : l2;

        // 返回新链表的头节点
        return dummyHead->next;
    }
};

4. 示例说明

示例一（题目中的例子）

输入：

l1 = 1->2->4, l2 = 1->3->4

输出：

1->1->2->3->4->4

示例二

输入：

l1 = 1->3->5, l2 = 2->4->6

输出：

1->2->3->4->5->6

以上就是如何使用C++合并两个有序链表的完整攻略。希望可以帮助大家理解并掌握这个重要的数据结构算法。