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 均按 非递减顺序 排列
思路分析
-
初始化：
-
如果
head1为空，直接返回head2。 -
如果
head2为空，直接返回head1。 -
创建两个指针
p1和q1，分别指向head1和head2。 -
创建一个虚拟头节点
newhead，值为0。这个虚拟头节点用于简化插入操作。 -
创建一个尾指针
tail，初始时指向newhead。
-
-
合并链表：
- 当
p1和q1都不为空时，进行比较和合并操作：-
如果
p1->val小于q1->val，将p1插入到tail的后面，然后更新tail和p1。 -
否则，将
q1插入到tail的后面，然后更新tail和q1。
-
-
更新
p2和q2以记录p1和q1的下一个节点。 -
继续循环直到
p1或q1为空。
- 当
-
处理剩余部分：
-
如果
p1为空，说明head1已经全部合并，将tail->next指向剩余的q1。 -
如果
q1为空，说明head2已经全部合并，将tail->next指向剩余的p1。
-
-
返回结果：
-
返回
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;}
};
