配列から連結リストを組み立てる【TypeScript】

はじめに

こんにちは！Shungiku です。
最近は就活のために専ら LeetCode の問題を解いていることが多いです。

さて、LeetCode では連結リストの問題（例えばこれとか）において、入力のサンプルが以下のような配列で与えられます。

head = [1,2,3,4]

一方、実際に Submit した場合、関数（またはメソッド）の引数で受け取る入力値は連結リストのヘッドのノードになっています。

ちなみにノードの構造は LeetCode では以下のように定義されています。

 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)
     }
 }

「入力サンプルの配列をListNodeを用いた連結リストに変換してくれるヘルパー関数がほしい！」というのが、本稿のモチベーションです。

そんなヘルパー関数があれば、Failしたケースについてデバッグする際、サクッと入力値を用意できて便利です。

実装

配列から連結リストを組み立てる関数は以下のようになります。

function buildList(array: number[]): ListNode | null {
    let next_node: ListNode | null = null
    
    const reversed = array.slice().reverse()

    reversed.forEach(val => { // （１）
        const node = new ListNode(val) // （２）
        node.next = next_node // （３）
        next_node = node // （４）
    })
    
    return next_node
}

引数で受け取る配列を後ろから処理しています。

例えば引数が [1, 2, 3, 4] だった場合、 [4, 3, 2, 1] の順で以下のように処理が進みます。

１ループ目

• （１）4 に対して処理を開始
• （２）ノードを生成（★）
• （３）★ノードの next に Keep してある next_node （初期値の null） を突っ込む
• （４）★ノードを next_node として Keep

２ループ目

• （１）3 に対して処理を開始
• （２）ノードを生成（★）
• （３）★ノードの next に Keep してある next_node （前ループで生成した 4 のノード） を突っ込む
• （４）★ノードを next_node として Keep

3ループ目...以下同文

まとめ

これで Fail したケースに対してのデバッグが捗るぜ...!

ちなみに木構造についても同様の記事を執筆してますので、以下ご参照ください。