【力扣 21】合并两个有序链表 C++题解（链表+双指针）

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

示例 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 均按 非递减顺序 排列

思路

首先，初始化两个指针p1和p2分别指向两个链表的头部。然后进入一个循环，只要两个链表都还有剩余元素，就比较p1和p2指向的当前元素的大小。如果p1指向的元素小于p2指向的元素，就将p1指向的元素插入新链表，并将p1向后移动一位。反之，就将p2指向的元素插入新链表，并将p2向后移动一位。

当其中一个链表的所有元素都已经插入新链表后，循环结束。这时，另一个链表可能还有剩余元素。因此，还需要两个额外的循环，分别将p1和p2指向的链表的剩余元素全部插入新链表。

插入元素的操作是通过一个名为"insert"的辅助函数实现的。如果新链表为空，就将新元素作为新链表的头部。否则，就将新元素插入新链表的尾部，然后将尾部指针向后移动一位。

最后，函数返回新链表的头部指针，即完成了两个有序链表的合并。

AC代码

/*
 * @lc app=leetcode.cn id=21 lang=cpp
 *
 * [21] 合并两个有序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
	ListNode* list3 = nullptr;
	ListNode* p3 = nullptr;

   public:
	ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
		ListNode* p1 = list1;
		ListNode* p2 = list2;
		while (p1 != nullptr && p2 != nullptr) {
			if (p1->val < p2->val) {
				insert(p1->val);
				p1 = p1->next;
			} else {
				insert(p2->val);
				p2 = p2->next;
			}
		}
		while (p1 != nullptr) {
			insert(p1->val);
			p1 = p1->next;
		}
		while (p2 != nullptr) {
			insert(p2->val);
			p2 = p2->next;
		}
		return list3;
	}
	void insert(int t) {
		if (list3 == nullptr) {
			list3 = new ListNode(t);
			p3 = list3;
		} else {
			p3->next = new ListNode(t);
			p3 = p3->next;
		}
	}
};
// @lc code=end