將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回诸蚕。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的踪宠。
輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
示例 2：
輸入：l1 = [], l2 = []
輸出：[]
示例 3：
輸入：l1 = [], l2 = [0]
輸出：[0]
提示：
兩個(gè)鏈表的節(jié)點(diǎn)數(shù)目范圍是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非遞減順序 排列
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有自赔。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處柳琢。
方法一：遞歸
思路
我們可以如下遞歸地定義兩個(gè)鏈表里的 merge 操作（忽略邊界情況绍妨，比如空鏈表等）：
也就是說，兩個(gè)鏈表頭部值較小的一個(gè)節(jié)點(diǎn)與剩下元素的 merge 操作結(jié)果合并柬脸。
算法
我們直接將以上遞歸過程建模他去，同時(shí)需要考慮邊界情況。
如果 l1 或者 l2 一開始就是空鏈表 倒堕，那么沒有任何操作需要合并灾测，所以我們只需要返回非空鏈表。否則垦巴，我們要判斷 l1 和 l2 哪一個(gè)鏈表的頭節(jié)點(diǎn)的值更小媳搪，然后遞歸地決定下一個(gè)添加到結(jié)果里的節(jié)點(diǎn)铭段。如果兩個(gè)鏈表有一個(gè)為空，遞歸結(jié)束蛾号。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
來源：力扣（LeetCode）
著作權(quán)歸作者所有稠项。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處鲜结。
方法二：迭代
思路
我們可以用迭代的方法來實(shí)現(xiàn)上述算法。當(dāng) l1 和 l2 都不是空鏈表時(shí)活逆，判斷 l1 和 l2 哪一個(gè)鏈表的頭節(jié)點(diǎn)的值更小精刷，將較小值的節(jié)點(diǎn)添加到結(jié)果里，當(dāng)一個(gè)節(jié)點(diǎn)被添加到結(jié)果里之后蔗候，將對(duì)應(yīng)鏈表中的節(jié)點(diǎn)向后移一位怒允。
算法
首先，我們?cè)O(shè)定一個(gè)哨兵節(jié)點(diǎn) prehead 锈遥，這可以在最后讓我們比較容易地返回合并后的鏈表纫事。我們維護(hù)一個(gè) prev 指針，我們需要做的是調(diào)整它的 next 指針所灸。然后丽惶，我們重復(fù)以下過程，直到 l1 或者 l2 指向了 null ：如果 l1 當(dāng)前節(jié)點(diǎn)的值小于等于 l2 爬立，我們就把 l1 當(dāng)前的節(jié)點(diǎn)接在 prev 節(jié)點(diǎn)的后面同時(shí)將 l1 指針往后移一位钾唬。否則，我們對(duì) l2 做同樣的操作侠驯。不管我們將哪一個(gè)元素接在了后面抡秆，我們都需要把 prev 向后移一位。
在循環(huán)終止的時(shí)候吟策， l1 和 l2 至多有一個(gè)是非空的儒士。由于輸入的兩個(gè)鏈表都是有序的，所以不管哪個(gè)鏈表是非空的檩坚，它包含的所有元素都比前面已經(jīng)合并鏈表中的所有元素都要大着撩。這意味著我們只需要簡(jiǎn)單地將非空鏈表接在合并鏈表的后面，并返回合并鏈表即可效床。
下圖展示了 1->4->5 和 1->2->3->6 兩個(gè)鏈表迭代合并的過程：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// 合并后 l1 和 l2 最多只有一個(gè)還未被合并完睹酌，我們直接將鏈表末尾指向未合并完的鏈表即可
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
}
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)剩檀，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處憋沿。
