1.算法題目
將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回优构。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的窄俏。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
2.算法思路
算法思路：
- 遞歸：兩個(gè)鏈表頭部較小的一個(gè)與剩下元素的 merge 操作結(jié)果合并涕刚，首先考慮邊界情況：如果 l1 或者 l2 一開始就是 null 末患，那么沒有任何操作需要合并伏恐，所以我們只需要返回非空鏈表咙咽。否則，我們要判斷 l1 和 l2 哪一個(gè)的頭元素更小媒峡，然后遞歸地決定下一個(gè)添加到結(jié)果里的值瘟栖。時(shí)間復(fù)雜度：O(n + m)O(n+m)，空間復(fù)雜度：O(n + m)O(n+m)丝蹭；
- 迭代：設(shè)定一個(gè)哨兵節(jié)點(diǎn) "prehead"慢宗，維護(hù)一個(gè) prev 指針，我們需要做的是調(diào)整它的 next 指針奔穿。然后镜沽，我們重復(fù)以下過程，直到 l1 或者 l2 指向了 null ：如果 l1 當(dāng)前位置的值小于等于 l2 贱田，把 l1 的值接在 prev 節(jié)點(diǎn)的后面同時(shí)將 l1 指針往后移一個(gè)元素缅茉；否則把 l2 的值接在 prev 節(jié)點(diǎn)的后面，同時(shí)將 l2 指針后移一個(gè)元素男摧；然后將 prev 向后移一個(gè)元素蔬墩。在循環(huán)終止的時(shí)候， l1 和 l2 至多有一個(gè)是非空的耗拓，最后將非空的值接在 prev 節(jié)點(diǎn)的后面拇颅，即可實(shí)現(xiàn)兩個(gè)有序鏈表的合并。
3.算法代碼
鏈表定義的代碼如下：
// 鏈表定義
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
根據(jù)遞歸的算法思路編寫的算法代碼如下：
// 遞歸實(shí)現(xiàn)
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
根據(jù)迭代的算法思路編寫的算法代碼如下：
// 迭代實(shí)現(xiàn)
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prevHead = new ListNode(-1);
ListNode prev = prevHead;
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;
}
prev.next = l1 != null ? l1 : l2;
return prevHead.next;
}
??如果你有疑問或更好的算法思路乔询，歡迎留言交流Ｕ敛濉！竿刁！
??如果感覺我的文章對您有所幫助黄锤，麻煩動(dòng)動(dòng)小手給個(gè)喜歡，謝謝Ｊ嘲荨Ｍ沂臁！
