連結リストが回文か調べる方法

世界で闘うプログラミング力を鍛える150問』から、回文に関する問題を解いていこう。

回文チェッカー

連結リストが回文 (先頭から巡回しても末尾から巡回しても、各ノードの要素がまったくおなじになっている) かどうかを調べる関数を実装してください。 (P.195)

この問題は「リストのサイズがあらかじめ分かっているかどうか」で難易度が変わる。サイズが分かっている場合、プログラムは簡潔になる。

(リストのサイズがあらかじめ分かっている場合の) 回文チェッカー

次のような方針で解ける。

  1. リストを先頭から順に半分まで読み込み、値をひとつずつスタックに詰める (リストのサイズが分かるから、「半分まで」が分かる)
  2. リストの半分より後と、「1.」のスタックをひとつずつポップしていった値を比較する

スタックは FILO (First-In, Last-Out) なので、最初に格納した値が最後に取り出される。つまり、「1.」で作ったスタックは、ポップするたびにリストの真ん中からひとつずつ先頭に向かって値を返すようになる。

実装

先の記述を素直に実装しただけのものだ。コメントも多めにつけたので、容易に理解できるだろう。

コメントを残す

コメントを投稿するには、以下のいずれかでログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中