21. 合并兩個有序鏈表

將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

示例 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. 在已有的鏈表 l1 上插入 l2（插入排序思想）
2. 重新從空節點開始構建鏈表

在已有的鏈表 l1 上插入 l2（插入排序思想）

1. 為什么會想到插入排序：插入排序的過程中，前半部分是有序的，后半部分的無序元素逐個插入前面的有序部分，這道題可以把 l1 視作排序完成的前半部分，l2 視作后半部分插入前半部分
2. 在這種做法下，其實相當于把兩個序列拼接起來后再排序
3. 需要一個當前遍歷到的 l1 元素的前一個元素的指針 preL1，便于插入 l2 元素；l2 元素在插入前應保存下一個要比較的 l2 元素 l2->next，否則無法接著遍歷 ListNode* temp = l2->next;
4. 使用假頭 dummyHead，確保可以插入 l1 的第一個元素前面
5. 遍歷 l1 元素時使用 preL1 = l1; l1 = l1->next;

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {//排除有空鏈表的情況if(!l1) return l2;if(!l2) return l1;ListNode* dummyHead1 = new ListNode(-101);dummyHead1->next = l1;ListNode* preL1 = dummyHead1;while(l1 && l2){while(l1 && l2->val >= l1->val){preL1 = l1;l1 = l1->next;}//此時l1為空；或者l2指向的節點比l1指向的節點小，比l1節點的前一個節點大if(!l1){//處理l1為空的情況preL1->next = l2;return dummyHead1->next;}//處理l2指向的節點比l1指向的節點小，比l1節點的前一個節點大的情況while(l2 && l2->val >= preL1->val && l2->val <= l1->val){preL1->next = l2;ListNode* temp = l2->next;l2->next = l1;preL1 = l2;l2 = temp;} }return dummyHead1->next;}
};

重新從空節點開始構建鏈表

• 首先定義一個假頭，然后比較 l1 和 l2 的元素，小的就添加在新鏈表的后面，不斷循環，最后當有一個鏈表為空就把剩下的都接在新鏈表的后面即可

class Solution {
public:ListNode* trainningPlan(ListNode* l1, ListNode* l2) {ListNode* dum = new ListNode(0);ListNode* cur = dum;while(l1 && l2){if(l1->val <= l2->val){cur->next = l1;cur = l1;l1 = l1->next;}else{cur->next = l2;cur = l2;l2 = l2->next;}}if(!l1) cur->next = l2;if(!l2) cur->next = l1;return dum->next;}
};