題目

題目翻譯

融合兩個排序過的連結串列為一個新的連結串列後回傳。

解題步驟

1. 問題描述：

   • 給定兩個已排序的鏈表 l1 和 l2，需要合併這兩個鏈表，使得合併後的鏈表仍然保持排序狀態。

2. 思路分析：

   • 使用一個虛擬的頭節點來簡化合併過程，然後利用兩個指針逐步比較 l1 和 l2 的值，將較小的節點連接到合併鏈表中。
   • 當一個鏈表遍歷結束後，將另一個鏈表的剩餘部分連接到合併鏈表的尾部。

3. 步驟分解：

   • 步驟1：創建一個虛擬節點 dummy 作為合併鏈表的頭節點，並設置一個指針 current 指向 dummy。
   • 步驟2：比較 l1 和 l2 的節點值：
     • 如果 l1 的節點值小於 l2，將 l1 的節點連接到 current，然後移動 l1 指針。
     • 否則，將 l2 的節點連接到 current，然後移動 l2 指針。
   • 步驟3：重複上述過程，直到遍歷完其中一個鏈表。
   • 步驟4：將剩餘的鏈表（如果有）連接到合併鏈表的尾部。
   • 步驟5：返回合併鏈表的頭節點，即 dummy->next。

改寫後的程式碼

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 創建虛擬節點
        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;

        // 逐步合併兩個鏈表
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                current->next = l1;  // 將 l1 的節點添加到合併鏈表中
                l1 = l1->next;       // 移動 l1 指針
            } else {
                current->next = l2;  // 將 l2 的節點添加到合併鏈表中
                l2 = l2->next;       // 移動 l2 指針
            }
            current = current->next; // 移動 current 指針
        }

        // 將剩餘的鏈表添加到合併鏈表中
        if (l1 != nullptr) {
            current->next = l1;
        } else {
            current->next = l2;
        }

        // 返回合併後的鏈表
        return dummy->next;
    }
};