I am the best ！！！

题目描述

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

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

思路分析

1. 初始化：

   • 如果 head1 为空，直接返回 head2。

   • 如果 head2 为空，直接返回 head1。

   • 创建两个指针 p1 和 q1，分别指向 head1 和 head2。

   • 创建一个虚拟头节点 newhead，值为 0。这个虚拟头节点用于简化插入操作。

   • 创建一个尾指针 tail，初始时指向 newhead。

2. 合并链表：

   • 当 p1 和 q1 都不为空时，进行比较和合并操作：

     • 如果 p1->val 小于 q1->val，将 p1 插入到 tail 的后面，然后更新 tail 和 p1。

     • 否则，将 q1 插入到 tail 的后面，然后更新 tail 和 q1。

   • 更新 p2 和 q2 以记录 p1 和 q1 的下一个节点。

   • 继续循环直到 p1 或 q1 为空。

3. 处理剩余部分：

   • 如果 p1 为空，说明 head1 已经全部合并，将 tail->next 指向剩余的 q1。

   • 如果 q1 为空，说明 head2 已经全部合并，将 tail->next 指向剩余的 p1。

4. 返回结果：

   • 返回 newhead->next，这是合并后的链表实际头节点，跳过虚拟头节点。

复杂度分析：

• 时间复杂度： O(m + n)，其中 m 和 n 分别是两个链表的长度。在最坏情况下，我们需要遍历两个链表的所有节点。

• 空间复杂度： O(1)，只使用了常数级别的额外空间。

完整代码

class Solution {
public:ListNode* mergeTwoLists(ListNode* head1, ListNode* head2) {if(head1==NULL)return head2;if(head2==NULL)return head1;auto p1=head1;auto q1=head2;auto newhead=new ListNode(0);auto tail=newhead;//尾指针//p1,q1有一个为空，就结束while(p1!=NULL&&q1!=NULL){auto p2=p1->next;auto q2=q1->next;if(p1->val<q1->val){//头插，把p1插入到尾指针的后面p1->next=tail->next;tail->next=p1;//tail往后走tail=tail->next;//p1往后走p1=p2;}else{q1->next=tail->next;tail->next=q1;tail=tail->next;q1=q2;}}if(p1==NULL){tail->next=q1;}else{tail->next=p1;}return newhead->next;}
};