來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/merge-two-sorted-lists/
題目描述
將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回拆挥。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。
題目分析
提供兩種方法：
- 遞歸
- 迭代
代碼實(shí)現(xiàn)
public class HeBingList21 {
public static void main(String[] args) {
HeBingList21 fanZhuanList206 = new HeBingList21();
ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
ListNode head2 = new ListNode(1, new ListNode(4, new ListNode(6, new ListNode(7))));
fanZhuanList206.mergeTwoLists(head, head2);
}
/**
* 遞歸
*
* @param l1
* @param l2
* @return
*/
public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val <= l2.val) {
l1.next = mergeTwoLists2(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists2(l1, l2.next);
return l2;
}
}
/**
* 時(shí)間復(fù)雜度：O(n+m)，其中 n 和 m 分別為兩個(gè)鏈表的長度绰筛。因?yàn)槊看窝h(huán)迭代中棉饶，l1 和 l2 只有一個(gè)元素會(huì)被放進(jìn)合并鏈表中拭宁， 因此 while 循環(huán)的次數(shù)不會(huì)超過兩個(gè)鏈表的長度之和聚假。所有其他操作的時(shí)間復(fù)雜度都是常數(shù)級(jí)別的碌廓，因此總的時(shí)間復(fù)雜度為 O(n+m)。
* <p>
* 空間復(fù)雜度：O(1)背传。我們只需要常數(shù)的空間存放若干變量呆瞻。
*
* @param l1
* @param l2
* @return
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) {
return null;
}
ListNode result = new ListNode(-1);
ListNode curr = result;
while (l1 != null || l2 != null) {
if (l1 == null) {
curr.next = l2;
l2 = l2.next;
} else if (l2 == null) {
curr.next = l1;
l1 = l1.next;
} else {
if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
}
curr = curr.next;
}
return result.next;
}
}
遞歸復(fù)雜度
- 時(shí)間復(fù)雜度：O(n+m)，其中 n 和 m 分別為兩個(gè)鏈表的長度径玖。
- 空間復(fù)雜度：O(n+m)痴脾。
迭代復(fù)雜度
時(shí)間復(fù)雜度：O(n+m)。因?yàn)槊看窝h(huán)迭代中挺狰，l1 和 l2 只有一個(gè)元素會(huì)被放進(jìn)合并鏈表中明郭， 因此 while 循環(huán)的次數(shù)不會(huì)超過兩個(gè)鏈表的長度之和。所有其他操作的時(shí)間復(fù)雜度都是常數(shù)級(jí)別的丰泊，因此總的時(shí)間復(fù)雜度為 O(n+m)薯定。
空間復(fù)雜度：O(1)。
好了瞳购，今天就到這里话侄，感謝各位看官到這里，不如點(diǎn)個(gè)關(guān)注吧学赛！
?
