經典串列題 合併已排序好的兩條串列 Merge Two Sorted Lists Leetcode #21

這題的題目在這裡:

題目敘述

題目會給我們兩條已經從小到大排序好的串列，要求我們依照從小到大的順序，合併這兩條串列。

測試範例

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

約束條件

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

演算法

其實這一題可以結合經典的雙指針、遞迴的技巧，簡潔的解開。

介面與參數:
list1, list2 分別指向兩條串列頭部當下要比較的位置

通則:
如果list1當下節點的值 比 list2當下節點的的值還小，則list1放在前面，並且list1指向下一回合次小的節點。

同樣的道理，對於另一種情況也是對稱的。

如果list2當下節點的值 比 list1當下節點的的值還小，則list2放在前面，並且list2指向下一回合次小的節點。

終止條件:
如果list2已經空了，那麼已經不需要比較和合併，直接回傳list1即可。

同樣的道理，對於另一種情況也是對稱的。

如果list1已經空了，那麼已經不需要比較和合併，直接回傳list2即可。

程式碼

class Solution:
　def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
　　
　　# List 1 is empty, then result is decided by List 2
　　if not list1:
　　　return list2
　　
　　# List 2 is empty, then result is decided by List 1
　　if not list2:
　　　return list1
　　
　　# General cases: compare node value, and update linkage
　　if list1.val < list2.val:
　　　list1.next = self.mergeTwoLists(list1.next, list2)
　　　return list1
　　　
　　else:
　　　list2.next = self.mergeTwoLists(list1, list2.next)
　　　return list2

複雜度分析

另 m, n 分別為list1, list2串列的長度

時間複雜度:

O( m+n ) 最長的長度就是每個節點交叉比大小，合併後的串列最後總長度為O(m+n)

空間複雜度:

O( m+n ) 最長的長度就是每個節點交叉比大小，遞迴stack最深所需空間為O(m+n)

關鍵知識點

關鍵在於，比較的時候，只要比較排頭即可，後續的比較都是依樣畫葫蘆，比較和合併模式是共通的。

Reference:

[1] Python/Go/Java/JS/C++ O( m + n ) simple recursion [w/ Comment] - Merge Two Sorted Lists - LeetCode