題目連結

題型解說

這是一題難度為簡單的題目

需要設計一個方法，此方法會傳入二個已經排好序的 Linked list

將兩個 Linked list 合併成一個 Linked list 並且排好序(小到大)後回傳

範例:

list1 = [1, 2, 3, 4]、list2 = [1, 2, 3, 4]，則回傳 [1, 1, 2, 2, 3, 3, 4, 4]

解題思路

我們利用一個 while 迴圈來運作，從兩個 list 中各取一個來比較

將比較小的 Node 串到要回傳的 Node 中後將該 list 的變數設為下一個 Node

用說的比較複雜，下面我們加上圖解來解釋

result 和 temp 指向同一個 Node

list1 和 list2 指向自己的 List 的開頭

接下來比較 list1 是不是小於等於 list2，如果是就將 list1 當下的 Node 移動到 result 下

然後將 list1變數 指向 list1 的下一個 Node，將 temp變數 指向最後的 Node

接下來比較 list1 是不是小於等於 list2，如果不是就將 list2 當下的 Node 移動到 result 下

然後將 list2變數 指向 list2 的下一個 Node，將 temp變數 指向最後的 Node

重複以上動作直到 list1 和 list2 都為 null 後就可以把 result 回傳了

程式碼

Java

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();
        ListNode temp = root;
        
        while (l1 != null || l2 != null) {
            if (l2 == null || (l1 != null && l1.val <= l2.val)) {
                temp.next = l1;
                l1 = l1.next;
            } else if (l1 == null || (l2 != null && l2.val < l1.val)) {
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }
        
        return result.next;
    }
}