1.題目
將兩個有序鏈表合并為一個新的有序鏈表并返回和二。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。
2.示例
輸入：
1->2->4, 1->3->4
輸出：
1->1->2->3->4->4
3.解法探析
3.1 解法 1：迭代法
3.1.1 解題思路
1.對于空鏈表耳胎，假如
鏈表 l1為空則返回鏈表 l2惯吕，鏈表 l2為空則返回鏈表 l1惕它。
2.比較鏈表 l1和鏈表 l2的第一個結點的值，將值小的結點保存下來作為合并后新鏈表的第一個結點废登，并把值小的結點的鏈表向后移動一位淹魄。
3.不斷在兩個鏈表剩下的結點中選擇較小的值，鏈接到新鏈表的后面堡距，直至某一個鏈表為空甲锡。
4.當兩個鏈表長度不同時，會有一個鏈表先為空羽戒，此時把另外一個鏈表剩下的結點都連接到新鏈表的末尾缤沦。
3.1.2 代碼實現
C++實現：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) {
return l2;
} else if (l2 == nullptr) {
return l1;
}
// 申請dummy指針作為一個虛擬的頭結點，并將其成員初始化為 -1
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1 == nullptr) {
cur->next = l2;
} else if (l2 == nullptr) {
cur->next = l1;
}
return dummy->next;
}
};
GO實現：
type ListNode struct {
Val int
Next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
// 如果有一個鏈表為 nil易稠，直接返回另一個鏈表
if l1 == nil {
return l2
} else if l2 == nil {
return l1
}
// 定義一個臨時的頭指針缸废，它的 Next 指向的結點才有數據
dummy := &ListNode{}
cur := dummy
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
cur.Next = l1
// cur 與 l1 都往后移動一位
// 相當于 l1 = l1.Next cur = cur.Next
cur, l1 = cur.Next, l1.Next
} else {
cur.Next = l2
cur, l2 = cur.Next, l2.Next
}
}
// 循環(huán)完之后，把鏈表剩下的結點直接放到后面驶社，因為鏈表本身就是有序的企量，所以鏈接在后面就行
if l1 == nil {
cur.Next = l2
} else if l2 == nil {
cur.Next = l1
}
return dummy.Next
}
3.1.3 復雜度分析
時間復雜度：（假設 n 為鏈表1的長度，m 為鏈表2的長度）
空間復雜度：
3.2 解法 2：遞歸法
3.2.1 解題思路
1.對于空鏈表亡电，假如
鏈表 l1為空則返回鏈表 l2届巩，鏈表 l2為空則返回鏈表 l1。
2.比較兩個鏈表中第一個結點的大小份乒，確定頭結點的位置恕汇。
3.頭結點確定后，繼續(xù)在兩個鏈表剩下的結點中選出較小的結點鏈接到第 2 步選出的結點后面冒嫡，然后再繼續(xù)重復 第 2拇勃、3 步，直到有鏈表為空孝凌。
3.2.2 代碼實現
C++實現：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) {
return l2;
} else if (l2 == nullptr) {
return l1;
}
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l2->next, l1);
return l2;
}
}
};
GO實現：
type ListNode struct {
Val int
Next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
// 如果有一個鏈表為 nil方咆，直接返回另一個鏈表
if l1 == nil {
return l2
} else if l2 == nil {
return l1
}
// 對ListNode類型進行一次 new 的實例化操作，也可以使用 dummy := new(ListNode) 進行實例化
dummy := &ListNode{}
// 獲取結構體實例的指針
newHead := dummy
if l1.Val < l2.Val {
newHead = l1
newHead.Next = mergeTwoLists(l1.Next, l2)
} else {
newHead = l2
newHead.Next = mergeTwoLists(l2.Next, l1)
}
return newHead
}
3.2.3 復雜度分析
時間復雜度：（假設 n 為鏈表1的長度蟀架，m 為鏈表2的長度）
空間復雜度：
個人主頁：
