LeetCode逐日精进：21.归并两个有序链表

标题链接：21.归并两个有序链表
标题形貌：
        将两个升序链表归并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的全部节点构成的。 

示例 1：

1. <strong>输入：</strong>l1 = [1,2,4], l2 = [1,3,4]
2. <strong>输出：</strong>[1,1,2,3,4,4]

复制代码

示例 2：

1. <strong>输入：</strong>l1 = [], l2 = []
2. <strong>输出：</strong>[]

复制代码

示例 3：

1. <strong>输入：</strong>l1 = [], l2 = [0]
2. <strong>输出：</strong>[0]

复制代码

提示：

• 两个链表的节点数量范围是 [0, 50]
  
• -100 <= Node.val <= 100
  
• l1 和 l2 均按 非递减次序 分列
  

思绪：可以参照之前的归并两个有序数组

1.     ListNode* l1 = list1;
2.     ListNode* l2 = list2;
3.     ListNode *newHead,*newTail;

复制代码

        界说l1指向链表1，l2指向链表2，l1，l2在两个链表中遍历举行比力。
        创建指向新链表首尾结点的指针newHead，newTail。
        比力两个链表中结点值的巨细，值小的结点尾插入新链表中，由于尾插必要判断当前链表是否为空，指向新链表头结点的指针必要改变，为了不让代码显得冗余，这里利用带头链表。

1.     //哨兵位
2.     newHead = newTail = (ListNode*)malloc(sizeof(ListNode));
3.     newHead->next = NULL;

复制代码

·        申请完空间后，将头结点的next指针置空，如许直接就能举行尾插，不必要再判断链表是否为空。
        在循环中：

1.         if (l1->val > l2->val)
2.         {
3.             newTail->next = l2;
4.             l2 = l2->next;
5.             newTail = newTail->next;
6.         }

复制代码

        若l1所指向的结点值大于l2，那么l2所指向的结点尾插入新链表，并将l2移向下一个结点。

1.        else
2.         {
3.             newTail->next = l1;
4.             l1 = l1->next;
5.             newTail = newTail->next;
6.         }

复制代码

        若l2所指向的结点值大于l1，那么l1所指向的结点尾插入新链表，并将l1移向下一个结点。
        当l1与l2中有一个指向空，即越界，跳出循环。

1.     while(l2)
2.     {
3.         newTail->next = l2;
4.         l2 = l2->next;
5.         newTail = newTail->next;
6.     }

复制代码

        当l1为空，将l2中剩余结点尾插入链表中。

1.     while(l1)
2.     {
3.         newTail->next = l1;
4.         l1 = l1->next;
5.         newTail = newTail->next;
6.     }

复制代码

        当l2为空，将l1中剩余结点尾插入链表中。

1.     return newHead->next;

复制代码

        末了，由于带头链表哨兵位的存在，返转头结点的下一个结点即可。
完备代码：

1. typedef struct ListNode ListNode;struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {    ListNode* l1 = list1;
2.     ListNode* l2 = list2;
3.     ListNode *newHead,*newTail;    //哨兵位
4.     newHead = newTail = (ListNode*)malloc(sizeof(ListNode));
5.     newHead->next = NULL;        while(l1 && l2)    {        if (l1->val > l2->val)
6.         {
7.             newTail->next = l2;
8.             l2 = l2->next;
9.             newTail = newTail->next;
10.         }        else
11.         {
12.             newTail->next = l1;
13.             l1 = l1->next;
14.             newTail = newTail->next;
15.         }    }    //l1为空    while(l2)
16.     {
17.         newTail->next = l2;
18.         l2 = l2->next;
19.         newTail = newTail->next;
20.     }    //l2为空    while(l1)
21.     {
22.         newTail->next = l1;
23.         l1 = l1->next;
24.         newTail = newTail->next;
25.     }    return newHead->next;}

复制代码