0021. Merge Two Sorted Lists - chasel2361/leetcode GitHub Wiki

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

在解這題之前必須先理解什麼是 singly-linked list (單向連結串列)，singly-linked list 是由許多個 ListNode 所形成，其定義如下：

    class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None

而單向連接串列的定義大概可以像下面這樣，輸入一個 list，輸出一個單項連結的節點

    def GenSinglyLinkedList(nums: list):
        nodes = [ListNode(n) for n in nums]
        for i in range(len(nodes) - 1):
            nodes[i].next = nodes[i+1]
        return nodes[0]

所以只要找到串列的頭，就可以(也只能)依序一個一個節點往下找到所有節點，所以上面的範例可以表示為

    # input
    l1 = GenListNode([1, 2, 4])
    l2 = GenListNode([1, 3, 4])
    
    #output
    l3 = GenListNode([1, 1, 2, 3, 4, 4])

因此，我們可以利用一個 dummy head (下稱 dummy ) 來指向第一個內容為 None 的暫時節點 cur，由於 dummy 僅單向指向 cur，cur 與其他節點串接不影響 dummy。

迭代法 (iteratively)

[1] 創造一個空的 dummy 將其指標指向游標解點 cur
[2] 依序比較 l1 及 l2 的值，將 cur.next 指向 val 較小的串列，並將 l1 或 l2 指向下一個節點
[3] 將 cur 指下一個節點 cur.next ，準備判斷下一個節點，此時 dummy 仍然指向原本的第一個節點
[4] 當 l1 或 l2 其中一個不存在之後，就不需要判斷了，直接把 cur.next 指向剩下的那一個串列
[5] 由於 dummy 指向 cur ，其 var 值不是我們需要的，所以回傳 dummy.next 即可

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 or not l2:
            return l2 or l1
    
        dummy = cur = ListNode(None)  # [1]
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next  # [2]
            else:
                cur = l2
                l2.next = l2.next  # [2]
            cur = cur.next  # [3]
        cur.next = l1 or l2  # [4]
        return dummy.next  # [5]

迭代法的時間及空間複雜度皆為O(N)

遞迴法 (recursively)

遞迴法的概念在於重複呼叫自身函式，在程式撰寫上較為簡潔，但時間與空間複雜度也較高，可以看這份文件 Python 初學第八講 — 遞迴 - ccClub

[1] 若 l1.val < l2.val ，重新呼叫本身函數，輸入 l1.next 及 l2 ，將 l1.next 指向其回傳值，會不停遞迴直至其中一個物件指向 None 為止

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 or not l2:
            return l2 or l1
            
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)  # [1]
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)  # [1]
            return l2

遞迴法的時間以及空間複雜度亦為O(N)

Code Link