Coding

LeetCode 21. Merge Two Sorted Lists

By Anthea / 芫荽 12月 21, 2022 3 min read

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:

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

Example 2:

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

Example 3:

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

最佳解：singly-linked list

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

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

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 中，最小的數字，當作第一個節點。有了第一個節點，接著才能往下建立。

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

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

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 為例：

// 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 ，繼續尋找。

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，就完成了。完整程式碼如下：

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%）

最佳解：singly-linked list

參考資料