[LeetCode]21-2つの秩序チェーンテーブルをマージ

21.2つの順序付きチェーンテーブルを結合し、2つの順序付きチェーンテーブルを新しい順序付きチェーンテーブルに結合して返します.新しいチェーンテーブルは、指定された2つのチェーンテーブルのすべてのノードを接合することによって構成されます.入力:1->2->4、1->3->4出力:1->1->2->3->4->4
解法1:チェーンテーブルを再帰的にマージする
この方法の実行時間は28%のコミットレコードを超えたにすぎない.

class Solution:
    def mergeTwoLists(self, l1, l2):
        def merge(l1, l2):
            if not l1:
                return l2
            if not l2:
                return l1
            if l1.val > l2.val:
                pres = l2
                pres.next = merge(l1, l2.next)
                return pres
            else:
                pres = l1
                pres.next = merge(l1.next, l2)
                return pres
        
        res = merge(l1, l2)
        return res

解法2:簡略化された再帰アルゴリズム
依然として再帰的な思想であり、82.57%を超える提出である.

class Solution:
    def mergeTwoLists(self, l1, l2):
        if not l1 or not l2:
            return l1 or l2
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2