劍指Offer算法題——合并兩個排序的連結清單

題目描述：

輸入兩個遞增排序的連結清單，合并這兩個連結清單并使新連結清單中的節點仍然是遞增排序的。

示例1：

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

方法：遞歸

思路：該題涉及到連結清單，我們不難想到要使用指針l1和l2和頭結點來進行周遊。.

        用于兩個連結清單都是遞增的，我們不需要考慮那麼多，隻需關注l1.val和l2.val的大小關系，來進行節點添加順序的指定。

        引入頭結點是因為：用于初始狀态合并連結清單中無節點，是以循壞第一輪時無法将節點添加到合并連結清單中。

算法：

1.先設定一個頭結點dummy，放到新連結清單前，最後傳回的就是dummy.next；設定cur為目前節點，從dummy開始

2.當兩個連結清單都非空時進入循環，令新連結清單的下一個節點cur.next為val更小的節點，相應的鍊

表節點後移一位

3.每次循環記得cur也要後移一位

4.如果循環結束後還有連結清單非空，cur指向非空連結清單

5.傳回dummy.next

代碼：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return dummy.next;
    }