LeetCodeのMerge Two Sorted Lists解いてみた

始めに

少し空いてしまったけど今回もLeetCodeの有名問題をやったのでアウトプットしていく
最近はMedium問題ばかりでしたが久々のEasy問題。
もし間違えなどがあればご指摘お願いします！

では行ってみよう

問題

2つのソート済み連結リストを結合して1つのソートされたノードを返す問題。
やり方を知らないとコーディングがピタリと止まる
当然私も止まった

考察

この問題を解く上で重要なのは2つのノードをどのようにして走査するのか？を考えること
最初に思いついたのが2回に分けてiteratorを使い値の配列を作り、それをマージした後に新たなノードを作成していく方法。
ただこれだと無駄な計算が多すぎる

なので2つのポインタ(curr, dummy)を使いlist1とlist2を同時に走査する方法を取る。
具体的には各ノードの値の小さい方の値のlistを先に進めながら走査していけば良い

解法

２つのポインタを用意

curr → 現在のポインタを示す
dummy → 最終的にマージしたノードのhead

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    curr = dummy = ListNode()

イテレート処理

list1とlist2の値を比較し、小さい方のノードを次のノードに設定する
この際、値の大きさが同じ場合、次のポインタにlist2を設定する

   while list1 and list2:
        if list1.val < list2.val:
            curr.next = list1
            list1 = list1.next
        else:
            curr.next =  list2
            list2 = list2.next

ノードを先に進める

前項で次のポインタは設定したのでノードを先に進めます

curr = curr.next

残りのノードを末尾に追加

残りのノードを追加したらdummy.nextでソートした連結リストの完成

curr.next = list1 or list2

return dummy.next

以下に全文を載せます

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    curr = dummy = ListNode()
    while list1 and list2:
        if list1.val < list2.val:
            curr.next = list1
            list1 = list1.next
        else:
            curr.next =  list2
            list2 = list2.next

        curr = curr.next 

    curr.next = list1 or list2

    return dummy.next

感想

連結リストの問題はやり方をある程度暗記でも良いのでは？と思ってる。
即興で解ければ苦労はないが、やはりコーディング面接や試験では時間制限などもあり本来なら解けた問題も緊張で解けないなんてことになったら大変。
なのである程度問題を見た時にざっくりの解法が浮かぶぐらいにはしておきたい
先は長い...