題目敘述
題目會給我們兩條已經從小到大排序好的串列，要求我們依照從小到大的順序，合併這兩條串列。
測試範例
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
list1andlist2are 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
