1 題目描述

合併兩個有序的鍊錶，並且返回一個新的鍊錶。新的鍊錶是由兩個鍊錶的節點組成的。

2 解法

跟 leetcode-2-add-two-numbers 很類似，因為它涉及到多個 listNode 的操作，並且將操作結果合併為一個，因此我們可以使用 dummy_head 來幫助我們串接結果。因為他是排序，所以要比較兩個數字的大小，但是我們最怕的是在取listNode的值時發現他是None而導致錯誤，因為題目說數字範圍是[0, 50] 因此我們取 100 當作最大值，因此我們可以使用 digit1 = list1.val if list1 else 100 的方式，儘管遇到 none 仍然可以繼續執行迴圈，直到兩個 list1 跟 list2 都觸底，以避免 None 的問題。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy_head = ListNode(-1)
        cur = dummy_head

        while list1 is not None or list2 is not None:
            # 檢查是否為 None，如果是 None 就取 100 以繼續迴圈
            digit1 = list1.val if list1 else 100
            digit2 = list2.val if list2 else 100

            # 操作：比較大小，取最小值，並且移動指標
            if digit1 <= digit2:
                min_val = digit1
                list1 = list1.next
            else:
                min_val = digit2
                list2 = list2.next

            cur.next = ListNode(min_val)
            cur = cur.next

        # 把 dummy_head 移除
        result = dummy_head.next
        dummy_head.next = None
        return result