はじめに
こんばんは．
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にもあげておきます．