題目
#

leetcode 21 - Merge Two Sorted Lists (題目說明請點連結)

題目簡述
#

合併兩個已排序的鏈表。

範例
#

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Explanation: 將兩個已排序的鏈表合併成一個新的已排序鏈表。

Example 2:

Input: list1 = [], list2 = []
Output: []
Explanation: 兩個空鏈表合併後仍為空鏈表。

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]
Explanation: 空鏈表與包含一個節點的鏈表合併。

解題思路
#

這題要求我們將兩個已排序的鏈表合併成一個新的已排序鏈表。我們需要比較兩個鏈表中節點的值，並按照升序排列。

解法
#

迭代法（Iterative Approach）

創建一個虛擬頭節點 res 和一個當前指針 cur
使用 while 迴圈遍歷兩個鏈表，直到其中一個或兩個都遍歷完畢
比較兩個鏈表當前節點的值，將較小的節點連接到結果鏈表
移動對應鏈表的指針到下一個節點
最後處理剩餘的節點（如果有的話）

步驟
#

創建虛擬頭節點 res 和當前指針 cur
當 list1 或 list2 不為空時，繼續迴圈：
- 如果 list1 為空，將 list2 的剩餘節點全部連接
- 如果 list2 為空，將 list1 的剩餘節點全部連接
- 如果兩個都不為空，比較節點值，連接較小的節點
移動當前指針到下一個位置
返回 res.next（跳過虛擬頭節點）

例子說明
#

list1 = [1,2,4], list2 = [1,3,4]

步驟	list1	list2	cur	res	操作說明
初始化	[1,2,4]	[1,3,4]	[0]	[0]	創建虛擬頭節點和當前指針
第1次比較	[2,4]	[1,3,4]	[0,1]	[0,1]	選擇list1的1，移動list1指針
第2次比較	[2,4]	[3,4]	[0,1,1]	[0,1,1]	選擇list2的1，移動list2指針
第3次比較	[4]	[3,4]	[0,1,1,2]	[0,1,1,2]	選擇list1的2，移動list1指針
第4次比較	[4]	[4]	[0,1,1,2,3]	[0,1,1,2,3]	選擇list2的3，移動list2指針
第5次比較	null	[4]	[0,1,1,2,3,4]	[0,1,1,2,3,4]	選擇list1的4，移動list1指針
處理剩餘	null	null	[0,1,1,2,3,4]	[0,1,1,2,3,4]	list1為空，連接list2剩餘節點
最終結果	-	-	-	[1,1,2,3,4,4]	返回res.next，跳過虛擬頭節點

完整程式碼
#

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 創建虛擬頭節點，用於簡化操作
        ListNode res = new ListNode();
        // 創建當前指針，用於遍歷和連接節點
        ListNode cur = res; 

        // 當兩個鏈表中任一個還有節點時，繼續迴圈
        while(list1 != null || list2 != null){
            
            // 如果list1為空，將list2的剩餘節點全部連接
            if(list1 == null){
                cur.next = list2;
                list2 = list2.next;
            }
            // 如果list2為空，將list1的剩餘節點全部連接
            else if(list2 == null){
                cur.next = list1;
                list1 = list1.next;
            }
            // 如果list1的值小於list2的值，選擇list1的節點
            else if(list1.val < list2.val){
                cur.next = list1;
                list1 = list1.next;
            }
            // 如果list2的值小於等於list1的值，選擇list2的節點
            else{
                cur.next = list2;
                list2 = list2.next;
            }
          
            // 移動當前指針到下一個位置
            cur = cur.next;
        }

        // 返回結果鏈表（跳過虛擬頭節點）
        return res.next;
    }
}