【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;
}