題目

https://leetcode.com/problems/merge-two-sorted-lists/

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

解答

C#

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null)
            return null;
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;

        if (l1.val <= l2.val)
        {
            l1.next = MergeTwoLists(l1.next, l2);
            return l1;
        }
        else
        {
            l2.next = MergeTwoLists(l1, l2.next);
            return l2;
        } 
    }
}

結果

Runtime: 88 ms, faster than 98.89% of C# online submissions.

Memory Usage: 24.9 MB, less than 6.45% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(1)

為什麼我要這樣做？

不知道大家以前上 資料結構 時，有沒有上過 LinkedList？

這題就是要實作簡化版的 LinkedList ── ListNode，並將兩個已經排序過的 ListNode merge 及排序。

What is ListNode?

故名思議就是將很多 node(節點) 串成一個 List 的資料結構。

1. 每一個 node 都有 val
2. 每一個 node 都會指向下一個 node (next)，直到下一個 node 為 null為止
3. 任何一個 node 都可以任意串接另一個 node(next) 或另一串 nodes
4. 任何一個 node 都可以很任性的拋下本來串接的 node(next)，直接結束這回合 node(next) = null

老實說我只記得資料結構的樣子，但是實作也忘得差不多了
所以一開始使用 while迴圈 去實作，如下

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public static ListNode MergeTwoLists(ListNode l1, ListNode l2)
    {
        ListNode result = new ListNode(0);
        ListNode current = result;

        if (l1 == null && l2 == null)
            return null;
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;

        while (l1 != null && l2 != null)
        {
            if (l1.val <= l2.val)
            {
                current.next = l1;
                l1 = l1.next;
            }
            else
            {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        current.next = l1 ?? l2;
        return result.next;
    }
}

1. 宣告一個 ListNode ，head 為 0
2. 宣告一個要準備來 merge 用的 current
3. 使用 while 迴圈判斷 l1 及 l2 是否還有值
   • 若 l1.val 小於 l2.val 則
     • current 要串接 l1
     • l1 改指向下一個 node(next) 準備做比較
   • 若 l1.val 大於等於 l2.val 則
     • current 要串接 l2
     • l2 改指向下一個 node(next) 準備做比較
   • current 改指向下一個 node(next) 準備到下一個迴圈做串接
4. 若 l1 還有剩下的 node，則串接到 current.next 上；否則將 l2 剩下的 node 串接到 current.next 上
5. 回傳 result 第2個 node(result.next)，因為我們起頭先接了一個 0 在前面

後來參考了討論區裡大神們的寫法，寫出 遞迴(recursion) 的最佳解

1. 如果 l1 為 null 及 l2 為 null，return null (這是來整人的吧？=.=)
2. 如果只有 l1 為 null ， return l2
3. 如果只有 l2 為 null ， return l1
4. 判斷 l1.val <= l2.val
   • 若是
     • l1.next 就要呼叫自己 MergeTwoLists(l1.next, l2) 去比較 l1.next 及 l2 的大小並串接
     • return l1，因為 l1 比較小要先串接
   • 否則
     • l2.next 就要呼叫自己 MergeTwoLists(l2.next, l1) 去比較 l2.next 及 l1 的大小並串接
     • return l2，因為 l2 比較小要先串接
5. 直到所有遞迴都 return 並結束

示意圖

如果看文字敘述不是很明確的話，可以看下面的示意圖。

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉