連結リストの走査で役立つランナーテクニックについてまとめる。

世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法で紹介されていて初めて知った。

ランナーテクニックとは

連結リストの先頭から走査していくポインタと、そのポインタより先から走査していくポインタの2種類を用意して、同時に走査していく方法。

これが何に役立つかというと、例えば次のような例題を解くのに役立つ。

例題

単方向連結リストの末尾からn番目の要素を見つけるアルゴリズムを実装しなさい。

このようにランナーテクニックを使うと時間計算量はO（N）、空間計算量はO(1）で解くことができる。

連結リストのノード数が決まっていればわざわざポインタを２つ用意しなくとも、（全ノード数-n）が末尾からn番目となるので単純に解けるが、そうでない場合はこのように解くか、再帰で解くことになる。再帰の場合は計算量が増えるはず・・

所感

コーディングクイズで使えるシーンがありそうなので頭の片隅に留めておきたい。