JZ16 --- 合并兩個排序的清單

題目描述：

輸入兩個單調遞增的連結清單，輸出兩個連結清單合成後的連結清單，當然我們需要合成後的連結清單滿足單調不減規則。

題解：

我們已知是兩個遞增的連結清單，需要把他合并成一個遞增的連結清單。

（1）我們需要一個結果連結清單，表示最後合并後的連結清單。

（2）周遊兩個連結清單，如果 cur1 < cur2，那麼就說明 list1 的目前結點小于 list2 的目前結點，那麼就需要把 cur1 排在前面，同時 cur1 也要後移。如果 cur1 >= cur2，那麼就說明 list1 的目前結點大于 list2 的目前結點，那麼就需要把 cur2 排在前面，同時 cur2 也要後移。

（3）我們需要注意的是，結果連結清單要繼續合并連結清單，那麼就需要一個 last 來标記目前結果連結清單的最後一個結點。last.next = cur ，就可以直接将我們比較得到的資料放置在連結清單末尾。

（4）重複步驟2，直至其中一個連結清單周遊結束。

cur1 > cur2

cur1 > cur2

周遊至 cur2 為空時，直接将 cur1 放置 res連結清單最末尾/。

最終得到合并之後的遞增連結清單

public ListNode Merge(ListNode list1, ListNode lis
    if(list1 == null){
        return list2;
    }
    if(list2 == null){
        return list1;
    }
    ListNode cur1 = list1;
    ListNode cur2 = list2;
    ListNode res = null;  //結果連結清單
    ListNode last = null;  //結果連結清單的最後一個結點
    while(cur1 != null && cur2 != null){
        if(cur1.val < cur2.val){
            if(res == null){
                res = cur1;
            }
            else{
                last.next = cur1;
            }
            // 更新 last 和 cur1
            last = cur1;
            cur1 = cur1.next;
        }
        else{
            if(res == null){
                res = cur2;
            }else{
                last.next = cur2;
            }
            // 更新 last 和 cur2
            last = cur2;
            cur2 = cur2.next;
        }
        // 更新位置之後，必然會在某時某個連結清單周遊結束
        // 如果 cur1 周遊結束，則直接把剩下的 cur2 跟在後面
        if(cur1 != null){
            last.next = cur1;
        }else{
            // 如果 cur1 周遊結束，則直接把剩下的 cur2 跟在後面
            last.next = cur2;
        }
    }
    return res;
}