LeetCode 021&劍指Offer 16 合并兩個有序連結清單

021 合并兩個有序連結清單 騰訊精選50

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

示例：

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

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

思路：建立一個新結點和新指針，指針指向頭結點，然後比較兩個連結清單的大小，小的就用指針指向，然後後移，繼續比較直到兩個連結清單周遊到null，列印新連結清單

代碼：

//定義指針
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2){
        //定義新的連結清單的頭結點
        ListNode newList = new ListNode(0);
        //定義一個新連結清單的頭指針
        ListNode cur =newList;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                cur.next=l1;
                cur=cur.next;
                l1=l1.next;
            }else{
                cur.next=l2;
                cur=cur.next;
                l2=l2.next;
            }
        }
        if(l1==null){
            cur.next=l2;
        }else{
            cur.next=l1;
        }
        return newList.next;//newList開頭有個多餘的0，是以傳回newList.next
    }
           

注意：最後為什麼不傳回newList，傳回newList.next,因為newList開頭有個多餘的0，是以傳回newList.next