#はじめに
こんばんは．
M1就活生がLeetCodeから，easy問題を中心にPythonを用いて解いていきます．

↓では，解いた問題のまとめを随時更新しています．
まとめ記事

#問題
今回解いたのは，難易度easyから問題21のMerge Two Sorted Lists です．
問題としては，ソートされたl1，l2をマージして，それらをソートしたリストとして返すというもの．この際，l1，l2と返却値であるソートしたリストには，次のようなクラス指定があります．

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

入力例と出力例は以下の通りです．

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: l1 = [], l2 = []
Output: []

Example 3:

Input: l1 = [], l2 = [0]
Output: [0]

#書いたコード
今回の問題では，再帰を使って書いてみました．
まずはじめに，片方のリストが空であれば，もう片方を返します．このとき，入力されるl1，l2はもともとソートされているので，今回の問題ではこのまま返すことができます．
次に，l1とl2の先頭要素を比較します．l1の方が小さければ，l1.nextとl2を入力として再帰呼び出しすることで，l1を前進させます．同様に，l2の方が小さければ，l1とl2.nextを入力として再帰呼び出しすることで，l2を前進させます．このとき，最終的には小さい値を最初の要素とするため，再帰呼び出し後，小さい方のリストを返します．

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

再帰を使わない方法での解法があったので，参考に書いてみました．
まず，マージするリストの先頭であるdummyと，どの値をdummyに追加すべきかを探すためのtmpを初期化します．
l1とl2がどちらも空でない場合に，l1とl2の先頭要素を比較します．どちらか一方が空の場合は，もう片方を返すようにするためです．l1，l2，tmpを進めていくことで，マージしたリストを作っていきます．

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    dummy = tmp = ListNode()
    while l1 and l2:
        if l1.val < l2.val:
            tmp.next = l1
            l1 = l1.next
        else:
            tmp.next = l2
            l2 = l2.next
        tmp = tmp.next
    tmp.next = l1 or l2
    return dummy.next

#おわりに
今回の問題は入力値，返却値の型指定など今までにないパターンだったので，色々と調べながら試行錯誤してみました．
pythonのコピーは癖があるものの，今回のような使い方もできるのかと勉強になりました．

今回書いたコードはGitHubにもあげておきます．

前回　次回