21 合并兩個有序連結清單

1. 問題描述：

将兩個升序連結清單合并為一個新的升序連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。 

示例：

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

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

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/merge-two-sorted-lists

2. 思路分析：

① 其實這道題目是連結清單題目中比較經典的題目，在循環中當兩個連結清單都不為空的時候周遊連結清單元素，使用一個前驅指針來記錄上一個節點這樣才好連接配接目前需要連接配接的節點（上一個節點的next指向目前較小的元素），在循環中判斷兩個連結清單目前節點的大小關系，pre節點的next指針域連接配接的較小的元素，當連接配接的是較小元素的時候，将該連結清單的指針往下移動一位，另外一個連結清單指向目前節點的指針不變

② 當退出循環之後将pre的next指針域連接配接到還有剩餘元素的連結清單上即可，整體的代碼難度不大

3. 代碼如下：

class Solution {
   public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 != null) return l2;
        if (l1 != null && l2 == null) return l1;
        ListNode pre = null, head = null;
        while (l1 != null && l2 != null){
            if (l1.val < l2.val){
                if (pre == null){
                    pre = l1;
                    head = l1;
                }
                else  {
                    pre.next = l1;
                    pre = l1;
                }
                l1 = l1.next;
            }else {
                if (pre == null){
                    pre = l2;
                    head = l2;
                }
                else {
                    pre.next = l2;
                    pre = l2;
                }
                l2 = l2.next;
            }
        }
        if (l1 != null && pre != null) pre.next = l1;
        if (l2 != null && pre != null) pre.next = l2;
        return head;
    }
}