一、題目介紹
本題為LeetCode的 Merge Two Sorted Lists。

給定兩個已經按照遞增順序排列的Linked List：list1、list2
需要將兩個Linked List合併成一個新的排序Linked List，並回傳合併後的頭節點。

例如：list1 = [1, 2, 4]、list2 = [1, 3, 4]
合併後：[1, 1, 2, 3, 4, 4]，也就是 1 → 1 → 2 → 3 → 4 → 4
如果其中一個Linked List已經走訪完畢，就可以直接將另一個Linked List剩餘的節點接到結果後方。

二、解題思路
因為兩個Linked List本身都已經排序，所以不需要重新排序。
可以使用兩個指標：p1 → list1，p2 → list2
每次比較：p1.val，p2.val
哪一個比較小，就將哪個節點接到合併後的Linked List，然後將對應的指標往後移動。

例如：
list1: 1 → 2 → 4
list2: 1 → 3 → 4

第一次：1 == 1，選擇其中一個1
接著比較2和1，選擇1
再比較2和3，選擇2
依照這個方式持續比較，最後得到1 → 1 → 2 → 3 → 4 → 4

核心概念
這題可以把兩條 Linked List 想成兩條已經排好隊伍的資料：

每次只需要看兩個指標目前指向的節點，選擇比較小的那一個。
因此不需要把所有資料重新放進陣列再排序。

三、解題流程
Step 1：建立Dummy Node
建立一個虛擬節點：dummy → null
它的目的主要是方便處理合併後Linked List的頭節點。

另外建立：current = dummy
代表目前合併結果的最後一個節點。

Step 2：比較兩個 Linked List
當
list1 != null
list2 != null
時，持續比較兩個節點的值。

如果list1.val < list2.val
就將list1接到current.next → current.next = list1
然後list1 = list1.next
讓list1往下一個節點移動，如果list2比較小，就進行相同操作。

Step 3：處理剩餘節點
當其中一個Linked List走完後，另一個可能還有剩餘節點。
這時可以直接接上current.next = list1或current.next = list2
因為剩下的部分本身已經排序完成，所以不需要再比較。

Step 4：回傳結果
最後回傳dummy.next，因為dummy本身只是輔助節點，真正的結果從dummy.next開始。

四、Java實作

五、Python實作

六、時間與空間複雜度
Java

• Time Complexity：O(n + m)
  • n為list1的節點數量。
  • m為list2的節點數量。
  • 最多需要走訪兩個Linked List中的所有節點。
• Space Complexity：O(1)
  • 只使用dummy、current等固定數量的額外變數。
  • 沒有建立與節點數量成正比的額外資料結構。
  • 合併時主要是重新連接原本的節點。

Python

• Time Complexity：O(n + m)
  • 每個節點最多被處理一次。
• Space Complexity：O(1)
  • 只使用固定數量的指標變數。
  • 不需要建立新的List來儲存所有結果。

七、Java與Python解法比較

1. Linked List的節點
   Java與Python都透過ListNode表示Linked List的節點。
   每個節點主要包含：val、next
   其中：

• val：目前節點儲存的值
• next：指向下一個節點
  因此 Linked List 的結構可以表示成：[1] → [2] → [4] → null

2. 節點移動方式
   Java：list1 = list1.next;
   Python：list1 = list1.next
   兩種語言的概念完全相同，都是透過next移動到下一個節點。

3. Linked List 與 Array 的差異
   Day3使用的是Array，而今天開始使用Linked List。

Array：

Linked List：

因此Linked List沒有像Array那樣直接透過索引快速存取任意位置的特性，但在節點連接與移動方面具有不同的使用方式。

4. Dummy Node
   Java 與 Python 都使用：dummy → ...
   Dummy Node是這題非常實用的技巧。
   它可以讓我們不用額外處理「第一個節點要怎麼加入」的特殊情況，只需要統一使用：
   current.next = ...
   最後再回傳：dummy.next即可。

5. 複雜度比較
   
   兩種語言使用的演算法相同，因此時間與空間複雜度也相同。

八、實作結果
LeetCode 測試結果：Accepted

九、今日學習心得
今天開始學習Linked List（鏈結串列），並透過Merge Two Sorted Lists了解如何操作節點與next指標。

與前幾天使用的Array不同，Linked List的資料不是透過索引直接存取，而是透過每個節點的next連接到下一個節點。因此在處理Linked List時，需要更加注意目前指標所指向的位置，以及節點之間的連接關係。

本題因為兩個Linked List原本就已經排序，所以不需要重新排序，只要比較兩個目前節點的值，再將較小的節點加入結果即可。

今天也學到了Dummy Node的使用方式。透過建立一個虛擬節點，可以簡化Linked List合併時的頭節點處理，讓程式邏輯更加一致。

今天的核心觀念：Linked List → next 指標 → 逐節點比較 → 重新連接節點。