力扣刷题--21.归并两个有序链表

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)，只使用了常数级别的额外空间。
  

完备代码

2. class Solution {
3. public:
4.     ListNode* mergeTwoLists(ListNode* head1, ListNode* head2) {
5.         if(head1==NULL)
6.             return head2;
7.         if(head2==NULL)
8.             return head1;
9.         auto p1=head1;
10.         auto q1=head2;
11.         auto newhead=new ListNode(0);
12.         auto tail=newhead;//尾指针
13.         //p1,q1有一个为空，就结束
14.         while(p1!=NULL&&q1!=NULL)
15.         {
16.             auto p2=p1->next;
17.             auto q2=q1->next;
18.             if(p1->val<q1->val)
19.             {
20.                 //头插，把p1插入到尾指针的后面
21.                 p1->next=tail->next;
22.                 tail->next=p1;
23.                 //tail往后走
24.                 tail=tail->next;
25.                 //p1往后走
26.                 p1=p2;
27.             }else{
28.                 q1->next=tail->next;
29.                 tail->next=q1;
30.                 
31.                 tail=tail->next;
32.                 q1=q2;
33.             }
34.         }
35.         if(p1==NULL){
36.             tail->next=q1;
37.         }else{
38.             tail->next=p1;
39.         }
40.         return newhead->next;
42.     }
43. };

复制代码