今天是紀錄LeetCode解題的第二十一天

第二十一題題目：

給定兩個已排序的鏈結串列list1和list2，合併兩個鏈結串列

解題思路

建立dummy節點當作虛擬開頭，用一個指針current指向dummy，當list1和list2都不為空時，比較兩個的val，current.next指向較小的值，接著把current和被選中的list移向下一個指針，當其中一個list為空時，current直接指向另一個list，最後回傳dummy.next(真正的鏈結串列的頭real head of the merged linked list)

程式碼

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:        
        dummy = ListNode(0)
        current = dummy

        while list1 and list2:
            if list1.val < list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next
        current.next = list1 if list1 else list2
        return dummy.next

執行過程

初始狀態

• dummy → None
• current → dummy
• list1:1 → 2 → 4
• list2:1 → 3 → 4

第一次執行

• list1.val < list2.val → 1 < 1 → False
• 執行：
  current.next = list2 #dummy.next -> 1 (list2)
  list2 = list2.next #list2 -> 3->4
  current = current.next #current -> 1 (list2)
• 狀態：
  dummy -> 1 -> None
  current -> 1
  list1: 1 -> 2 -> 4
  list2: 3 -> 4

第二次執行

• list1.val < list2.val → 1 < 3 → True
• 執行：
  current.next = list1 #1(list2).next -> 1(list1)
  list1 = list1.next #list1 -> 2->4
  current = current.next #current -> 1(list1)
• 狀態：
  dummy -> 1 -> 1 -> None
  current -> 1 (list1)
  list1: 2 -> 4
  list2: 3 -> 4

第三次執行

• list1.val < list2.val → 2 < 3 → True
• 執行：
  current.next = list1 #1(list1).next -> 2
  list1 = list1.next #list1 -> 4
  current = current.next #current -> 2
• 狀態：
  dummy -> 1 -> 1 -> 2 -> None
  current -> 2
  list1: 4
  list2: 3 -> 4

第四次執行

• list1.val < list2.val → 4 < 3 → False
• 執行：
  current.next = list2 #2.next -> 3
  list2 = list2.next #list2 -> 4
  current = current.next #current -> 3
• 狀態：
  dummy -> 1 -> 1 -> 2 -> 3 -> None
  current -> 3
  list1: 4
  list2: 4

第五次執行

• list1.val < list2.val → 4 < 4 → False
• 執行：
  current.next = list2 #3.next -> 4
  list2 = list2.next #list2 -> None
  current = current.next #current -> 4
• 狀態：
  dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> None
  current -> 4
  list1: 4
  list2: None

最後跳出迴圈，接上剩餘的list1

• current.next = list1 # 4.next -> 4
• 最終鏈結串列：dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4
• return dummy.next：1 -> 1 -> 2 -> 3 -> 4 -> 4

核心觀念：current與dummy都是指向同一條鏈表的「節點」

• dummy是鏈表的「起點」
• current是我們用來遍歷和修改鏈表的指標
• 現在兩個變數都指向同一個節點（dummy節點）
• 重要：鏈表是物件（reference type），所以我們改current.next，實際上改的是dummy.next的內容。