【LeetCode】わかっていても使えない再帰関数

こんにちは、Tochiです。 LeetCodeをしていて苦戦していた問題の答えを見ていたときに膝から崩れ落ちたものがあったので アウトプットしてきます。

問題

2 つのソートされたリンクリスト list1とlist2の先頭 が与えられます 2 つのリストを 1 つの並べ替えられたリストにマージします。このリストは、最初の 2 つのリストのノードを結合して作成する必要があります。 マージされたリンク リストの先頭を返します。

例 1:

入力: list1 = [1,2,4]、list2 = [1,3,4]

出力: [1,1,2,3,4,4]

例 2:

入力: list1 = 、list2 =

出力:

例 3:

入力: list1 = 、list2 = [0]

出力: [0]

制約:

• 両方のリストのノード数は [0, 50]の範囲内です
• -100 <= Node.val <= 100
• list1とは両方とも降順ではないlist2順にソートされます。

回答

これを特には再帰的なアルゴリズムを即座に考えられないとまずいです。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  if (l1 === null) { return l2 }
  if (l2 === null) { return l1 }

  if (l1.val < l2.val) 
       { l1.next = mergeTwoLists(l1.next, l2); return l1 } 
  else { l2.next = mergeTwoLists(l1, l2.next); return l2 }
}

答えを見たらそれはそうだとなるのですが、 この再帰的アルゴリズムを即座に思いつくのって中々できなかったりする。 大学とかだとこの辺しっかり学ぶが、久しく忘れていた。。

再帰的アルゴリズムを利用しないとなると。。

自分が最初に考えていたのはこんな感じ。

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {    
    const dummyHead = new ListNode();
    let ptr = dummyHead, p1 = list1, p2 = list2;

    while (p1 && p2) {
        if (p1.val < p2.val) {
            ptr.next = p1;
            p1 = p1.next;
        } else {
            ptr.next = p2;
            p2 = p2.next;
        }
        ptr = ptr.next;
    }
    ptr.next = p1 ?? p2;

    return dummyHead.next;
};

普通にこれでも正解ではあるが最適解ではない。 実際、ランタイムはめっちゃ遅い。

まとめ

この辺のアルゴリズムについてはもう一度勉強し直す。。