連結リストで循環する部分の最初のノードを返すアルゴリズム

今日も『世界で闘うプログラミング力を鍛える150問』の問題を一つ解こう。

お題

循環する連結リストが与えられたとき、循環する部分の最初のノードを返すアルゴリズムを実装してください。 (P.192)

考え方

連結リストが循環するか調べるための手段に「ファストランナー」と「スローランナー」を使うものがある。スローランナーは連結リストをひとつずつ、ファストランナーは連結リストをふたつずつ移動するものだ。連結リストが循環するなら、ファストランナーがスローランナーと重なるタイミングがある。

では、「循環する部分の最初のノード」を取得するにはどうすればいいだろう。

説明のため『世界で闘うプログラミング力を鍛える150問』の中から図を引用する (ノードの番号は説明の都合で追加した)。図の n1 はファストランナー、n2 はスローランナーだ。

連結リストのループ

スローランナーが k 進んでループに入るとき、ファストランナーは「循環する部分の最初のノード」から k だけ進んでいることになる。ここから順を追って考えていこう。

  1. ファストランナーはスローランナーより k だけ進んでいる
  2. ファストランナーは (LOOP_SIZE – k) だけ進めばスローランナーに追いつける
  3. ファストランナーがスローランナーに追いつくとき (上図で「n1 と n2 はここで出会う」とある箇所)、ループ内で (LOOP_SIZE – k) だけ進んだことになる

ここで次のふたつのポインタを用意する。

  1. ファストランナーがスローランナーに追いつく箇所を指すポインタ (すなわち、「n1 と n2 はここで出会う」とあるノードを指すポインタ)
  2. 連結リストのはじめを指すポインタ

それぞれをひとつずつ進めていき、交差するところが「循環する部分の最初のノード」だ。

実装

文章で説明した内容を Python で実装すると次のようになる。コメントを多めに書いたので、本記事の内容と照らし合わせて追うといいだろう。

コメントを残す

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

WordPress.com ロゴ

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

Twitter 画像

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

Facebook の写真

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

Google+ フォト

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

%s と連携中