題目

  • 題目連結
  • 目標函式 : mergeTwoLists(list1, list2)
    • Input : list1: Optional[ListNode]、list2: Optional[ListNode]
    • Output : Optional[ListNode]

解題概念

  • 題意 : 給予兩個 sorted Link List 1 : list1 與 Link List 2 : list2，需要對兩者進行 merge 成一 sorted Link List
  • 此題即是在 Merge Sort 中 Merge two runs into one run 的過程

我的寫法

  • 想法 :
    • res 當作是結果Link List 的開頭處，t 當作是結果Link List 的結尾處
    • 用 while 迴圈依序判斷 list1 與 list2 所指向的元素，直到 list1 == None 與 list2 == None
    • 每一回合需要判斷 :
      • 若 list1 == None : 把 list2 剩餘的元素加到 t
      • 若 list2 == None : 把 list1 剩餘的元素加到 t
      • 若 list1 != None 與 list2 != None :
        1. 比較 list1.val 與 list2.val 之大小
        2. 將較大的數字加入 t 中
        3. 將該 Link List 往後一格
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    def mergeTwoLists(self, list1, list2):
        
        t = ListNode()
        res = t

        while list1 != None or list2 != None:
            target = ListNode()
            if list1 == None:
                target = list2
                list2 = None
            elif list2 == None:
                target = list1
                list1 = None
            else: # list1 != None and list2 != None
                if list1.val <= list2.val:
                    target.val = list1.val
                    list1 = list1.next
                else:
                    target.val = list2.val
                    list2 = list2.next
            
            t.next = target
            t = t.next
        
        return res.next
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 30 ms (faster than 17.36%)
    • Memory Usage: 13.4 MB (more than 67.28%)

解答 or 其他優秀寫法 - Iteration 版

  • 想法 : 基本上與我的想法相同

解答 or 其他優秀寫法 - Recursion 版

  • 想法 :
    • 每一回合遞迴要去做以下判斷 :
      • 若 list1.val <= list2.val : 則對 list1.next 與 list2 去做 mergeTwoLists()，並將結果回傳至 list1.next，最後 return list1
      • 若 list1.val > list2.val : 則對 list1 與 list2.next 去做 mergeTwoLists()，並將結果回傳至 list2.next，最後 return list2
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def mergeTwoLists(self, list1, list2):
        
        if not list1: return list2

        if not list2: return list1

        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 23 ms (faster than 62.63%)
    • Memory Usage: 13.3 MB (more than 95.10%)