【LittleDuck_LeetCodeNote】21 - Merge Two Sorted Lists

Question and Hints

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Input: list1 = [], list2 = []
Output: []

Input: list1 = [], list2 = [0]
Output: [0]

• The number of nodes in both lists is in the range [0, 50].
• 100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

First Solution

💡 題目上方的註解是在提示你所使用的程式語言，它的Node結構長怎樣，
所以不用取消註解，不然反而會顯示 NoSuchMethodError
回到解題，這個題目我有點印象，是對LinkedList進行MergeSort。
不過有點久沒寫就忘記了，而且我也沒有用Java寫過。

我最初的想法是，用4個指標，L1、L2不斷向後搜尋，當作陣列搜尋進度。
H1、H2則當作合併時的參考點。

如果L1的值大於L2，L2就繼續往後找。
如果L1的值小於或等於L2，就要開始進行合併，合併的步驟如下：

1. 將L1指標向右移，此時L1表示下一個要搜尋的值，H1表示當下要進行合併的值
2. H1指向L2，進行合併
3. H2指向H1，表示陣列的頭
4. H1指標移向L1，做為下一次合併的參考點。

不過這遇到了一些問題，
包含H2參考點仍然會越來越後面，導致最後無法回到陣列的頭，
以及Java沒有指標，而是用Node物件去進行操作的方式讓我有點混亂，
所以很可惜，第一次沒有解出來。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
        // empty condition.
        if(list1 == null && list2 == null)
            return list1;
        if(list1 == null)
            return list2;
        if(list2 == null)
            return list1;

        // Deal with link problem.

        ListNode headL1 = new ListNode();
        headL1 = list1;
        ListNode headL2 = new ListNode();
        headL2 = list2;

        while(list1 != null || list2 != null){
            if(list1.val <= list2.val){
                list1 = list1.next;
                headL1.next = list2;
                headL2 = headL1;
                headL1 = list1;
            }
            else if(list1.val > list2.val){
                list2 = list2.next;
            }
        }
        return headL2;
    }
}

Upgrade Solution

💡 遞迴，神奇的遞迴，OMG。

其實不用特別處理陣列為空的狀況，
此範例是合併在list1，所以兩個都空，回傳哪一個都可以，
list1為空，回傳list2的值，
而無論是list2為空，還是要回傳整理好的陣列，
都是回傳list1。

這個遞迴的運作方式，畫成圖表是長這樣：

用遞迴的方式，讓函式本身從每一輪都挑出比較小的那個值，最後遞迴結束後再反向回傳，就能得到由小到大的回傳結果。

神技。Orz

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1!=null && list2!=null){
            if(list1.val < list2.val){
                list1.next = mergeTwoLists(list1.next,list2);
                return list1;
            }
            else{
                list2.next = mergeTwoLists(list1,list2.next);
                return list2;
            }
        }
        if(list1==null)
            return list2;
            
        return list1;
    }
}

Upgrade Solution 2

💡 這個做法就解決了前面「陣列的頭跑掉」的問題，
而它不是合併在list1或list2，
而是用了一個新陣列prehead依大小吞食兩個陣列。

• 這邊用prehead作為固定不動，永遠指在最前面的標頭，用cur作為向後追蹤的參考點。
• 吞食的方式是一個一個吃，只要list1的值比較小，就將list1放進陣列，list2的值比較小，就將list2放進陣列，看是放進哪一個陣列的值，該陣列的指標就向後移一格，同時cur每吃掉一個值就往後移一格。
• 當一個陣列空了以後，檢查兩個陣列還有沒有值，有就接在cur的後面。
• 最後回傳固定在陣列頭的prehead。

class Solution {
     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);
        ListNode cur = prehead;

        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 ? l2 : l1;
        return prehead.next;
    }
}