Leetcode-21. 2つの整列チェーンテーブルをマージ(python)

Leetcode-21. 2つの順序付きチェーンテーブルを結合

問題説明

Method 1

Method 2

問題の説明
2つの順序付きチェーンテーブルを新しい順序付きチェーンテーブルに結合して返します.新しいチェーンテーブルは、指定された2つのチェーンテーブルのすべてのノードを接合することによって構成されます.
例:
入力:1->2->4、1->3->4出力:1->1->2->3->4->4
チェーンテーブルノード定義:

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

Method 1
反復:新しいノードheadを作成し、2つのチェーンテーブルを巡り、ノードが指す位置を比較し、head後のノードに小さなノード値を割り当て、最終的にマージされたチェーンテーブルを得る

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(None)
        s = head
        while l1 or l2:
            if l1 is None:
                s.next = l2
                break
            if l2 is None:
                s.next = l1
                break
            if l1.val > l2.val:
                s.next = ListNode(l2.val)
                l2 = l2.next
            else:
                s.next = ListNode(l1.val)
                l1 =l1.next
            s = s.next
        return head.next

実行結果:実行時間:48 ms;メモリ消費量:13.7 MB時間複雑度:O(m＋n);空間複雑度:O(1)
Method 2
再帰:2つのチェーンテーブルのmerge操作(空のチェーンテーブルなどの境界を無視する)の2つのチェーンテーブルのヘッダの小さい1つと、残りの要素のmerge操作結果とを再帰的に定義できます.

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

実行結果:実行時間:40 ms;メモリ消費量:13.8 MB時間複雑度:O(n+m);空間複雑度:O(n+m)
参照リンク:反復と再帰の違い:https://blog.csdn.net/liuchaoxuan/article/details/79967578