LeetCode / Merge Two Sorted Lists

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

以下のように定義される、ListNodeというclassを使う問題です。ListNodeを使う問題はLeetCodeで大量に出てきます。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

回答・解説

解法1

ListNodeって何？Listと違うの？と思いながら、私がとりあえず書いたコードを示します。 内容は単純にIterationを回すものですが、これでも正解ではあります。

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

解法2

解法1のようにIterationを回す解法と対照的なのが、recursive（再帰的）な解法です。 再帰関数とは何か？については以下を参考にしていただければと思いますが、
一言で言えば、状態（引数の値）を変えながら、自分自身を呼び続ける関数のことを意味します。
（初めて再帰関数を見たときは意味がわからず軽く発狂しそうになりました。。。）

qiita.com

さて、このrecursiveな解法は以下の通りです。
l1とl2の各要素の大小を比較し、l1の1つ目の要素の方が小さければ、次はl1の2つ目の要素とl2の1つ目の要素の大小を比較し、
l2の1つ目の要素の方が小さければ、次はl2の2つ目の要素とl1の1つ目の要素の大小を比較します。
このように各要素の大小を比較し小さい方を採用する処理は何度も呼ばれることになるので、再帰関数で記述するのが効率的だということになります。

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