題目描述

將兩個有序鏈表合并為一個新的有序鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，

示例：

輸入：1 -> 2 -> 4 ，1 -> 3 -> 4

輸出：1 -> 1 -> 2 -> 3 -> 4 -> 4

方法 1：遞回

思路

特殊的，如果 l1 或者 l2 一開始就是 null ，那么沒有任何操作需要合并，所以我們只需要回傳非空鏈表，

終止條件：兩條鏈表分別名為 l1 和 l2，當 l1 為慷訓 l2 為空時結束

回傳值：每一層呼叫都回傳排序好的鏈表頭

本級遞回內容：如果 l1 的 val 值更小，則將 l1.next 與排序好的鏈表頭相接，l2 同理
O( m + n )，m 為 l1 的長度，n 為 l2 的長度

代碼實作

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //如果 l1 或者 l2 一開始就是 null ，說明不需要合并，所以我們只需要回傳非空鏈表
        if(l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }
        //如果11的val值更小，則將11.next與排序好的鏈表頭相接，12同理
        if(l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            //每一層呼叫都回傳排序好的鏈表頭
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

圖解演算法

方法二：迭代

思路

我們假設 l1 元素嚴格比 l2元素少，我們可以將 l2 中的元素逐一插入 l1中正確的位置，

首先，我們設定一個哨兵節點 "prehead" ，這可以在最后讓我們比較容易地回傳合并后的鏈表，我們維護一個 prev 指標，我們需要做的是調整它的 next 指標，

然后，我們重復以下程序，直到 l1 或者 l2 指向了 null ：如果 l1 當前位置的值小于等于 l2 ，我們就把 l1 的值接在 prev 節點的后面同時將 l1 指標往后移一個，否則，我們對 l2 做同樣的操作，不管我們將哪一個元素接在了后面，我們都把 prev 向后移一個元素，

在回圈終止的時候， l1 和 l2 至多有一個是非空的，由于輸入的兩個鏈表都是有序的，所以不管哪個鏈表是非空的，它包含的所有元素都比前面已經合并鏈表中的所有元素都要大，這意味著我們只需要簡單地將非空鏈表接在合并鏈表的后面，并回傳合并鏈表，

代碼實作

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //先初始化一個預先指標 prehead，該指標的下一個節點指向真正的頭結點head，是用來定位頭結點的
        listnode prehead = new listnode(-1);
        listnode prev = prehead;
        //遍歷串列l1和l2，直到全部遍歷完畢
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                //prev.next始終指向比較之后的那個小的，l2同理
                prev.next = l1;
                //當前位置的l1后移一位
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        //在回圈終止的時候， l1 和 l2 至多有一個是非空的，
        //需要將非空鏈表接在合并鏈表的后面，并回傳合并鏈表，
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}