【C/C++】合并两个有序链表（leetcode T21）

核心考点预览：链表（双指针）技巧：虚拟头结点

题目描述：

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

	输入	输出
示例1	l1 = [1,2,4], l2 = [1,3,4]	[1,1,2,3,4,4]
示例2	l1 = [], l2 = []	[]
示例3	l1 = [], l2 = [0]	[0]

提示：

• 两个链表的节点数目范围是 [0, 50]

• -100 <= Node.val <= 100

• l1 和 l2 均按非递减顺序排列

详细解答：

// 定义链表节点结构
struct ListNode {
    int val; // 节点值
    struct ListNode *next; // 下一个节点指针
};

// 合并两个升序链表
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode *p1 = list1, *p2 = list2; // 初始化指向两个链表的指针
    struct ListNode* res = (struct ListNode*)malloc(sizeof(struct ListNode)); // 结果链表头节点
    struct ListNode* p = res; // p指针用于构建结果链表

    // 遍历两个链表，逐个比较节点值，合并到结果链表
    while (p1 != NULL && p2 != NULL) {
        // 如果list1当前节点小于list2当前节点
        if (p1->val < p2->val) {
            p->next = p1; // 将list1的当前节点链接到结果链表
            p = p1; // 更新p指针，指向list1当前节点
            p1 = p1->next; // list1向后移动一位
        } 
        // 如果list1当前节点等于list2当前节点
        else if (p1->val == p2->val) {
            p->next = p1; // 将list1的当前节点链接到结果链表
            p = p1; // 更新p指针，指向list1当前节点
            p1 = p1->next; // list1向后移动一位

            p->next = p2; // 将list2的当前节点链接到结果链表
            p = p2; // 更新p指针，指向list2当前节点
            p2 = p2->next; // list2向后移动一位
        }
        // 如果list2当前节点小于list1当前节点
        else {
            p->next = p2; // 将list2的当前节点链接到结果链表
            p = p2; // 更新p指针，指向list2当前节点
            p2 = p2->next; // list2向后移动一位
        }
    }

    // 如果list1遍历完，直接将剩余的list2链接到结果链表
    if (p1 == NULL) {
        p->next = p2;
    }
    // 如果list2遍历完，直接将剩余的list1链接到结果链表
    if (p2 == NULL) {
        p->next = p1;
    }

    // 返回合并后的链表，从res->next开始
    return res->next;
}

这么写中间有些繁琐，我们可以如此修改：

// 定义链表节点结构
struct ListNode {
    int val; // 节点值
    struct ListNode *next; // 下一个节点指针
};

// 合并两个升序链表
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode *p1 = list1, *p2 = list2; // 初始化指向两个链表的指针
    struct ListNode* res = (struct ListNode*)malloc(sizeof(struct ListNode)); // 结果链表头节点
    struct ListNode* p = res; // p指针用于构建结果链表

    // 遍历两个链表，逐个比较节点值，合并到结果链表
   while (p1 != nullptr && p2 != nullptr) {

            // 比较 p1 和 p2 两个指针
            // 将值较小的的节点接到 p 指针
            if (p1->val > p2->val) {
                p->next = p2;
                p2 = p2->next;
            } else {
                p->next = p1;
                p1 = p1->next;
            }
            // p 指针不断前进
            p = p->next;
        }

    // 如果list1遍历完，直接将剩余的list2链接到结果链表
    if (p1 == NULL) {
        p->next = p2;
    }
    // 如果list2遍历完，直接将剩余的list1链接到结果链表
    if (p2 == NULL) {
        p->next = p1;
    }

    // 返回合并后的链表，从res->next开始
    return res->next;
}