Tag

【遞歸】【迭代】【鏈表】

---

題目來源

21. 合并兩個(gè)有序鏈表

---

題目解讀

合并兩個(gè)有序鏈表。

---

解題思路

一種樸素的想法是將兩個(gè)鏈表中的值存入到數(shù)組中，然后對(duì)數(shù)組進(jìn)行升序排序，最后將排序好的數(shù)組還原回鏈表，這是一種可行的思路，但是沒有充分利用題目已知的兩個(gè)鏈表有序的條件，大家可以自行嘗試，練習(xí)基礎(chǔ)語法與建立鏈表節(jié)點(diǎn)的知識(shí)。

方法一：遞歸

我們記兩個(gè)鏈表的頭節(jié)點(diǎn)分別為 l1 和 l2，在合并兩個(gè)鏈表的時(shí)候會(huì)遇到以下三種情況：

• l1 為空，直接返回 l2；
• l2 為空，直接返回 l1;
• 兩節(jié)點(diǎn)都不為空，那么又會(huì)分為兩種情況:
  • l1 節(jié)點(diǎn)值小于 l2 節(jié)點(diǎn)值，那么 l1 節(jié)點(diǎn)將會(huì)是合并后的節(jié)點(diǎn)新的頭節(jié)點(diǎn)，剩下的部分是 l1->next 和 l2 合并的節(jié)點(diǎn)，而合并 l1->next 和 l2 是合并 l1 和 l2 的子問題，也可以使用 mergeTwoLists 函數(shù)來解答，于是有 l1->next = mergeTwoLists(l1->next, l2)，并返回 l1；
  • 同理，l2 節(jié)點(diǎn)值小于 l1 節(jié)點(diǎn)值時(shí)，有 l2->next = mergeTwoLists(l1, l2->next)，并返回 l1。
• 以上這種將問題轉(zhuǎn)換為原問題的子問題的方法，稱為遞歸方法。遞歸方法是一種邊調(diào)用邊填充的方法。

實(shí)現(xiàn)代碼

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (list1 == nullptr) {return list2;}else if (list2 == nullptr) {return list1;}else if (list1->val < list2->val) {list1->next = mergeTwoLists(list1->next, list2);return list1;}else {list2->next = mergeTwoLists(list1, list2->next);return list2;}} 
};

python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:if l1 is None:return l2elif l2 is None:return l1elif l1.val < l2.val:l1.next = self.mergeTwoLists(l1.next,l2)return l1else:l2.next = self.mergeTwoLists(l1, l2.next)return l2        

復(fù)雜度分析

時(shí)間復(fù)雜度：$O(m+n)$，$m$ 和 $n$ 分別為兩個(gè)鏈表的長度，每個(gè)節(jié)點(diǎn)都是被遞歸調(diào)用一次。

空間復(fù)雜度：$O(m+n)$，每調(diào)用一次函數(shù) mergeTwoLists 都需要消耗?？臻g，棧空間的大小取決于遞歸調(diào)用的深度。

方法二：迭代

迭代的方法是一種相對(duì)容易理解的方法。為了方便實(shí)現(xiàn)，我們定義一個(gè)啞節(jié)點(diǎn) dummy，ListNode* dummy = new ListNode(-1);，最后只需要返回 dummy->next。

我們?cè)俣x一個(gè)節(jié)點(diǎn) prev 用來指向當(dāng)前值較小的節(jié)點(diǎn)，初始 prev = dummy，我們迭代枚舉兩鏈表中的節(jié)點(diǎn)：

• prev 指向值較小的節(jié)點(diǎn)；
• 值較小的節(jié)點(diǎn)更新為下一個(gè)節(jié)點(diǎn)，方便下一對(duì)節(jié)點(diǎn)的比較；
• prev 更新為下一個(gè)節(jié)點(diǎn)，為存放下一個(gè)更小的節(jié)點(diǎn)做準(zhǔn)備；
• 如果有一個(gè)鏈表為空了，直接退出迭代循環(huán)；
• 需要注意這時(shí)候，兩個(gè)鏈表中可能還有一個(gè)鏈表非空，需要將剩下的非空部分接在 prev 后面。

以上就是本題的迭代方法。

實(shí)現(xiàn)代碼

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* dummy = new ListNode(-1);ListNode* prev = dummy;while(list1 && list2){if(list1->val < list2->val){prev->next = list1;list1 = list1->next;}else{prev->next = list2;list2 = list2->next;}prev = prev->next;}prev->next = list1 ? list1 : list2;return dummy->next;}
};

python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:dummy = ListNode(-1)prev = dummywhile l1 and l2:if l1.val < l2.val:prev.next = l1l1 = l1.nextelse:prev.next = l2l2 = l2.nextprev = prev.nextprev.next = l1 if l1 is not None else l2return dummy.next

復(fù)雜度分析

時(shí)間復(fù)雜度：$O(m+n)$，$m$ 和 $n$ 分別為兩個(gè)鏈表的長度，每個(gè)節(jié)點(diǎn)都是被遞歸調(diào)用一次。

空間復(fù)雜度：$O(1)$。

---

寫在最后

如果文章內(nèi)容有任何錯(cuò)誤或者您對(duì)文章有任何疑問，歡迎私信博主或者在評(píng)論區(qū)指出 💬💬💬。

如果大家有更優(yōu)的時(shí)間、空間復(fù)雜度方法，歡迎評(píng)論區(qū)交流。

最后，感謝您的閱讀，如果感到有所收獲的話可以給博主點(diǎn)一個(gè) 👍 哦。