題目描述：

將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。 

示例：

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

具體如下圖：

即，將 L1 和 L2 鏈表進行合并。

思路1：遞歸

每次比較 l1 和 val 和 l2 的 val，誰小，就繼續(xù)循環(huán)他的 next 節(jié)遞歸進行比較，且返回值作為小節(jié)點的 next。
終止條件，就是 l1 為 null 或者 l2 為 null，任意一者為 null，都應(yīng)當返回另一者（肯定不為 null，且有序）。

算法空間復雜度和時間復雜度都是 O（n+m）；

圖示：

代碼如下：

static public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        if (l1.val < l2.val) {
            // 如果 l2 比 l1 大, 那 l1 的 next 就是 返回值(升序).
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

思路 2：循環(huán)

剛剛上面說了，每次都是比較 L1 的 val 和 L2 的 val，誰小，就繼續(xù)拿小節(jié)點的 next 節(jié)點和當前節(jié)點比較。

這個思路也可以用在循環(huán)中。

代碼如下：

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        ListNode dummy = new ListNode(0);

        ListNode pre = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                pre.next = l1;
                l1 = l1.next;
            } else {
                pre.next = l2;
                l2 = l2.next;
            }
            pre = pre.next;
        }

        if (l1 == null) {
            pre.next = l2;
        } else {
            pre.next = l1;
        }

        return dummy.next;
    }

我們在循環(huán)中，每次比較 L1 的值和 L2 的值，誰小，就更新誰的指針——繼續(xù)比較他的 next。

同時，我們定義一個虛擬節(jié)點，用于保存合并后的鏈表指針。

用一個 pre 節(jié)點，保存迭代的前指針。目的是讓前指針保存經(jīng)過排序的 節(jié)點。

最后，如果出現(xiàn)了 null 值，就將非 null 值鏈接到表尾。

返回虛擬節(jié)點的 next，就是排序后的數(shù)據(jù)。

算法空間復雜度 O1，時間復雜度 O（n + m）；

總結(jié)

該題的解法關(guān)鍵在于：每次循環(huán)或遞歸，都應(yīng)當找到兩個節(jié)點中，較小的那個，然后繼續(xù)比較較小的那個 next 節(jié)點。