> ## Content Index
> Fetch the complete content index at: https://blog.anthea.day/llms.txt
> Use this file to discover other available public pages before exploring further.

# LeetCode 21. Merge Two Sorted Lists
- URL: https://blog.anthea.day/leetcode-c-e5-88-b7-e9-a1-8c-e7-ad-86-e8-a8-98-3/
- Published: 2022-12-21T15:06:42.000Z
- Updated: 2026-11-07T18:26:11.000Z
- Author: Anthea / 芫荽
- Tags: #Migrated-1792241843742, #Import 2026-10-17 12:57, Coding, LeetCode 刷題筆記

> You are given the heads of two sorted linked lists `list1` and `list2`.

> Merge the two lists in a 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.

**Example 1:**

```ruby
Input: list1 = [1,2,4], list2 = [1,3,4] 
Output: [1,1,2,3,4,4]
```

**Example 2:**

```ruby
Input: list1 = [], list2 = [] 
Output: []
```

**Example 3:**

```ruby
Input: list1 = [], list2 = [0] 
Output: [0]
```

---

### 最佳解：singly-linked list

拿到題目就知道沒有想法，直接參考別人的解答。

提示說明需要使用的物件 ListNode 建立方法：

```csharp
public class ListNode { 
    public int val; 
    public ListNode next; 
    public ListNode(int val=0, ListNode next=null) { 
        this.val = val; 
        this.next = next; 
    } 
}
```

首先，取得在 `list1` 和 `list2` 中，最小的數字，當作第一個節點。有了第一個節點，接著才能往下建立。

取得最小數字的情況分成四種：

1. `list1 == null`：利用 `list2.val` 拿 `list2` 現在的值，拿出來之後就把 `list2` 替換成下一個值（`list2 = list2.next`）
2. `list2 == null`：同上
3. `list1 != null && list2 != null`：比較 `list1.val` 和 `list2.val` 的大小，誰小就拿誰，等於的話拿其中一邊即可

```csharp
public ListNode MergeTwoLists(ListNode list1, ListNode list2) { 
    var min = GetMinNode(ref list1, ref list2); 
} 
 
private static int GetMinNode(ref ListNode list1, ref ListNode list2) 
{ 
    int min; 
    if (list1 == null) 
    { 
        min = list2.val; 
        list2 = list2.next; 
    } 
    else if (list2 == null) 
    { 
        min = list1.val; 
        list1 = list1.next; 
    } 
    else if (list1.val < list2.val) 
    { 
        min = list1.val; 
        list1 = list1.next; 
    } 
    else 
    { 
        min = list2.val; 
        list2 = list2.next; 
    } 
    return min; 
}
```

找到最小值之後就建立第一個節點，利用另外一個變數 `current` 去記錄現在更新到哪個節點後，開始跑迴圈。迴圈在做的事情，就是找到下一個最小值，拿出來當成 `current` 的下一個值（`current.next`），以 Example 1 為例：

```csharp
// list1 = [1, 2, 4] / list2 = [1, 3, 4] 
var min = GetMinNode(ref list1, ref list2); 
 
// n = 1 
// list1 = [2, 4] / list2 = [1, 3, 4] 
var head = new ListNode(n); 
var current = head; 
 
while (list1 != null || list2 != null) 
{ 
    // list1 = [2, 4] / list2 = [1, 3, 4] 
    var nextMin = GetMinNode(ref list1, ref list2); 
 
    // nextMin = 1 
    // list1 = [2, 4] / list2 = [3, 4] 
    current.next = new ListNode(nextMin); 
 
    // current.next.val = 1 
    // current.next.next = null 
    current = current.next; 
}
```

這時候 `current.next.val` 等於我們找到的下一個最小值 `1`，`current.next.next` 則是因為還沒有塞入任何下一個值，所以是 `null`。為了繼續找下一個，我們把 `current` 的值改成 `current.next` ，繼續尋找。

```csharp
while (list1 != null || list2 != null) 
{ 
    // list1 = [2, 4] / list2 = [3, 4] 
    var nextMin = GetMinNode(ref list1, ref list2); 
 
    // nextMin = 2 
    // list1 = [4] / list2 = [3, 4] 
    current.next = new ListNode(nextMin); 
 
    // current.next.val = 2 
    // current.next.next = null 
    current = current.next; 
}
```

因為在 `GetMinNode` 內，我們利用 `list.next` 取出下一個值放回 `list` 內，而 `list.next` 是允許 `null` 的，也就是說，當 `list == null` 時，代表我們已經把所有值都取完了，因此 `list == null` 就是迴圈結束的條件。

最後，在整段程式碼前面先判斷過一次 list1 != null 和 list2 != null，就完成了。完整程式碼如下：

```csharp
if (list1 == null && list2 == null) return null; 
 
var min = GetMinNode(ref list1, ref list2); 
var head = new ListNode(min); 
 
var current = head; 
while (list1 != null || list2 != null) 
{ 
    var nextMin = GetMinNode(ref list1, ref list2); 
 
    current.next = new ListNode(nextMin); 
    current = current.next; 
} 
 
return head;
```

結果：Runtime 81 ms（97.56%） / Memory 40 MB（7.66%）

---

#### 參考資料

- [21\. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/description/?ref=blog.anthea.day)
- [C# 88 ms, faster than 94.28% of C#](https://leetcode.com/problems/merge-two-sorted-lists/solutions/593845/c-88-ms-faster-than-94-28-of-c/?ref=blog.anthea.day)