0021 - Merge Two Sorted Lists

大意

就是把已經排序的兩個 LinkedList 合併到一個 LinkedList，且要保持順序

實際作法

由於自己做出來都是 Timeout，應該是哪裡做錯了，以下附上正確的 Code:

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        
        head = ListNode()
        current = head

        while list1 != None and list2 != None:
            if list1.val <= list2.val:
                current.next = list1
                temp = list1.next
                current = list1
                list1 = temp
            else:
                current.next = list2
                temp = list2.next
                current = list2
                list2 = temp
        
        if list1 != None:
            current.next = list1
        if list2 != None:
            current.next = list2

        return head.next

建立一個新的 LIstNode 當作假的起頭（真正的起頭在假起頭的下一個），然後去比較兩個當前  ListNode 代表的數字

• 如果  list1 的數字比較小，或等於 list2，則新  list 的 next 必須是 list1
• 然後原本  list1 換成 list1 的下一個，也就是 list1.next
• 否則，新 list 的 next 必須為 list2，然後原本 list2 換成 list2.next
• 以此類推，直到  list1 或 list2 其中一個的值是 None (null)
• 但是 list1 或 list2 無論剩餘 LinkedList 的 Node 數量有多少，只要其中一個不是 None (null)，就直接接到新 ListNode 的最後就好（畢竟都排序過了）

然後回傳假的起頭的下一個，就是排序好的 LinkedList！