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