線形リストから重複する要素を削除

世界で闘うプログラミング力を鍛える150問』の問題を解いている。

今回のお題だ。

ソートされていない連結リストから、重複する要素を削除するコードを書いてください。

(発展問題) もし、一時的なバッファが使用できないとすれば、どうやってこの問題を解きますか?

重複したノードの削除

先に実装を示そう。

rootNode クラスのオブジェクトだ。Nodevalnext をメンバに持つ。next は連結リストでの次のノードを指している。

ロジックは単純だ。リストをたどりながら新しい値を used に足していき、もし next_nodeused の値が含まれていればリストから外している。

一時的なバッファが使用できない場合

一時的なバッファ (used) を使わないので、空間効率がよくなる。逆に時間効率は問われていない。遠慮なく二重ループを使ってしまおう。

リストをたどりつつ、val と同じ値を持つノードを現在のノードより後ろから消していくだけだ。

実行可能なソースコード

実行可能なサンプルも載せておこう。

コメントを残す

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

WordPress.com ロゴ

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

Twitter 画像

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

Facebook の写真

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

Google+ フォト

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

%s と連携中