題目描述
將兩個升序鏈表合并為一個新的升序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的玫锋。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
題目解析
方法一：遞歸
解題思路
我們直接采用遞歸的方法，首先判斷其中一個鏈表是否為空亭畜，若為空則無需進行遞歸比較直接返回結果劲件。否則比較鏈表 l1 和鏈表 l2 的頭元素哪個更小，將較小元素作為頭節(jié)點窿撬，然后遞歸比較較小元素后的鏈表與另一鏈表，直至兩鏈表元素都經過比較叙凡。
代碼示例
Java：
/**
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 1. terminator 遞歸終止條件
if (l1 == null) return l2;
if (l2 == null) return l1;
// 2. process data 處理當前層邏輯
if (l1.val < l2.val) {
// 3. drill down 遞歸到下一層
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l2.next, l1);
return l2;
}
}
復雜度分析
時間復雜度：O(m+n)
空間復雜度：O(m+n)
方法二：迭代
解題思路
我們采用迭代的方式來解決該問題劈伴，首先我們需要新建一個哨兵元素 newHead 用來當做合并后的鏈表頭節(jié)點。然后遍歷比較鏈表 l1 和鏈表 l2 元素握爷，將元素較小者賦值到合并后的鏈表上跛璧，直至完成兩鏈表元素之間的比較严里。
代碼示例
Java：
/**
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 1. 新建哨兵節(jié)點
ListNode newHead = new ListNode(-1);
// 2. 迭代比較兩鏈表元素
ListNode curr = newHead;
while(l1 != null && l2 != null) {
if (l1.val < l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
// 3. 處理未比較元素
curr.next = l1 == null ? l2 : l1;
return newHead.next;
}
復雜度分析
時間復雜度：O(m+n)
空間復雜度：O(1)
