【LittleDuck_LeetCodeNote】21 - Merge Two Sorted Lists

Question and Hints

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

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

Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []

Output: []

Example 3:

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

Output: [0]

Constraints:

• 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;

    }

}

⏰ Runtime: ?? ms (?? %)

📦 Memory: ?? MB (?? %)

---

Upgrade Solution

recursive.

💡 遞迴，神奇的遞迴，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;

    }

}

⏰ Runtime: 0 ms (100 %)

📦 Memory: 41.8 MB (86.38 %)

---

Upgrade Solution 2

4 Nodes, like first solution.

💡 這個做法就解決了前面「陣列的頭跑掉」的問題， 而它不是合併在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;

    }

}

⏰ Runtime: 0 ms (100 %)

📦 Memory: 42.6 MB (20.37 %)