題目連結(https://leetcode.com/problems/merge-two-sorted-lists/description/)
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.

1. Repeat（題目重複確認）

• 輸入：兩個已排序的 linked list，list1 and list2
• 輸出：返回合併後的 linked list 及 head
• 前提：兩 linked list 都是 non-decreasing

2. Examples（舉例確認理解）

舉例用的兩個 linked list 大小不要相等，相等的話 trace code 時會比較難解釋。

Input: list1 = [1,3,5], list2 = [2,6]
Output: [1,2,3,5,6]

3. Approach（解題思路）

方法 1：遞迴法

• 從頭開始比較 list1 and list2
• 如果list1->val 較小，此排序位即為 list1 中的數，將其放入新的 linked list，並從list1->next當作新的引數繼續做遞迴。
• 時間複雜度：O(m+n)
• 空間複雜度：O(m+n)

方法 2：迭代法

• 當list1 and list2 非空時，如果list1->val 較大，將 tail 的下一位指向list1->val ，list1 前進一位，反之亦然。結束比較後，tail 往前一位。
• 時間複雜度：O(m+n)
• 空間複雜度：O(1)

4. Code（C++）

方法 1：遞迴法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1) return list2;
        if(!list2) return list1;

        if(list1->val < list2->val){
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else{
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
            
    }
};

方法 2：迭代法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0); //虛擬的頭
        ListNode* tail = &dummy; //指向結果鏈表的尾部
        while(list1 && list2){
            if(list1->val <= list2->val){
                tail->next = list1; // 將較小的節點連接到結果鏈表
                list1 = list1->next; // 移動到下一個節點
            }else{
                tail->next = list2;  // 將較小的節點連接到結果鏈表
                list2 = list2->next; // 移動到下一個節點
            }
            tail = tail->next;
        }  
        tail->next = list1 ? list1 : list2; //list1非空 tail 則接回list1 ，空則接回list2
        return dummy.next;
    }    
};

5. Test

迭代步驟：

6. 相關題目與延伸概念

• LeetCode 23. Merge k Sorted Lists
• LeetCode 21. Merge Two Sorted Lists
• LeetCode 148. Sort List
• 進一步學習：使用 priority queue/heap 合併多個排序鏈表

7. 補充：語法＆注意事項

語法

1. tail->next = list1 ? list1 : list2;

   • 三元運算子寫法，等價於：

     if (list1 != nullptr) //list非空
         tail->next = list1; //將tail接到list1
     else
         tail->next = list2;
     

2. ListNode dummy(0);

   • 創建虛擬節點，避免處理 head 為空的特殊情況。

3. tail = tail->next;

   • 將 tail 指針移到最後一個節點，方便接下一個。

注意事項

• 空間複雜度的改進方案為迭代法 : O(1)。
• 遞迴法雖然簡潔，但規模大時可能會 stack overflow
• 比較時用 <= 寫法較穩定
  • 如果兩個節點值相同，保持 list1 節點在前