【第十三天 - 递回题目分析】

先简单回顾一下，今天预计分析的题目：

题目连结：https://leetcode.com/problems/merge-two-sorted-lists/

题目叙述：

题目有两个已经排序好的 linked list，你要将这两个 linked list 合并成一个已排序过的 linked list

测资的 Input/Output：

会拿到两个 linked list，需要合并後回传
这一题可以使用递回或迭代的方法实作，我们接下来会依序介绍
- 递回方法：将大问题分解成小问题
  - 大问题：两个 linked list 要排序
  - 分解成，每次只比对2个 linked list的数字，从这两个数字找出比较小的，剩下的数字交给下一个 function 决定
  - 以 input l1 = [1,4] 跟 l2 = [2] 为例
    - [1, 4] 和 [2] 的合并结果 = 先比较 1 与 2，得到比较小的 1 (会得到 [1])，然後加上剩下的 [4] 与 [2] 的合并结果
    - [4] 和 [2] 的合并结果 = 先比较 4 与 2，得到比较小的 2 (会得到[2])，然後加上剩下的 [4] 与 [] 的合并结果
    - [4] 和 [] 的合并结果 = 由於 l2 为空，直接得到 l1 的 [4]
  - 所以整个程序逻辑
    1. 先判断 l1 或 l2 是不是为空，若 l1 空了，那就 return l2，反之亦然 (终止条件) (注意，终止条件要先写，避免程序永远停不下来)
    2. 会一个一个比较 l1 与 l2 的值
      1. 若 l1 比较小，那这个值会留下来，然後将 l1 下一个数字与 l2 数字为参数，再呼叫一次自身函数 (再执行一次步骤1与2)
      2. 若 l2 比较小，那这个值会留下来，然後将 l1 与 l2 下一个数字为参数，再呼叫一次自身函数 (再执行一次步骤1与2)
```
class Solution:            
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
#       若 l1 为空，就没必要比较，直接回传 l2，反之亦然
        if l1 == None: 
            return l2;
        if l2 == None: 
            return l1;

#       判断 input 的 l1 与 l2 第一个值谁比较大   (随着每次呼叫自己，l1与l2会越来越短)
        if l1.val < l2.val: 
#           l1 比较小，所以 l1 第一个值留下来，把 l1.next (第二个)值 跟 l2 再执行一次自身 function
            l1.next = self.mergeTwoLists(l1.next, l2);
#           此时 return 的 l1 会是整串的，会包含 与 l2 相比，vl 这个比较小的值(第一个值)，还有 self.mergeTwoLists(l1.next, l2) 後的结果
            return l1;

        else:
            l2.next = self.mergeTwoLists(l1, l2.next);
            return l2;
```
- 迭代方法：
  1. 先创立一个叫 merge 的空 Linked list (排序过後的内容，都会储存在此)
  2. 使用回圈的方式，一个一个比较 l1 与 l2 的值，直到 l1 或 l2 其中一个为空
    1. 若 l1 比较小，就让 merge 接上当前 l1 的节点
    2. 若 l2 比较小，就让 merge 接上当前 l2 的节点
  3. 若 l2 空了，那就会将剩余的 l1 整串资料，接到 merge 尾端，反之亦然

class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
#       产生一个 ListNode 型态的 linked list，并且 val 里面塞 None  (next 预设为 None)
        merge = ListNode(None)
#       用一个 pointer 指向 linked list尾端，随着不断 merge，将永远指向 merge linked list 尾端来新增 node
        cursor = merge
#       若 l1 跟 l2 都不为空，则进行比较
        while l1 and l2:
#           比较 l1 跟 l2 的第一个元素 val，比较小的则加入 cursor 中，并将 後面的 linked list 覆盖上原 linked list (所以比较小的数字会消失)
            if l1.val <= l2.val:
                cursor.next = l1
                l1 = l1.next
            elif l1.val > l2.val:
                cursor.next = l2
                l2 = l2.next
            cursor = cursor.next
#       若 l2 空了，则将剩下的 l1 全部接到尾端，反之亦然
        if l1:
            cursor.next = l1
        else:
            cursor.next = l2

        return merge.next