2005年11月13日
アルゴリズムパズル（リンクリスト）
- 固定リンク
- コメント (2)
- トラックバック (7)
- カテゴリー:技術メモ
久しぶりに、プログラマもしくはソフトウェアエンジニアにしか分からない話。
同僚から教えてもらったアルゴリズムの問題。面白かったので、とりあえず問題だけメモ。
単方向リンクリスト（連結リスト）がある。ノード数を n とするが、n の値は分からない。リスト中にループ（循環参照）が存在するか否かを O(n) で判定するアルゴリズムを示せ。ただし、リストの各ノードの内容を変更してはならない。つまり、単純にポインタが指したノード全てにマーキングをしておいて、新しいノードに移るたびにマーキングされているかを調べることで判定することは出来ない。
反応と要望があれば、1週間後ぐらいに解答編を書きます。
- 固定リンク
- コメント (2)
- トラックバック (7)
- カテゴリー:技術メモ
Trackback on "アルゴリズムパズル（リンクリスト）"
以下7件のトラックバックはこのページのエントリー"アルゴリズムパズル（リンクリスト）"を参照しています。
このエントリーのトラックバックURL:
» [dev] 循環参照の O(n) による検索
- 2005年11月15日 20:12
- from is BUG ready ?
[http://www.cotton-tree.com/garyu/archives/2005/11/post_156.html:title] 発見しただけ。 ... [続きを読む]
» アルゴリズムパズル（リンクリスト）に答える
- 2005年11月16日 06:52
- from 猪股健太郎の雑記
「諸悪の根源は物理的」より： 単方向リンクリスト（連結リスト）がある。ノード数を n とするが、n の値は分からない。リスト中にループ（循環参照）が存在するか... [続きを読む]
» [program] 単方向linked listの循環参照判定をO(n)で行なう
- 2005年11月16日 09:41
- from やねうらお−よっちゃんイカを買いに行ったついでに家を買う男
「諸悪の根源は物理的」より。(id:ladybug:20051116経由) http://www.cotton-tree.com/garyu/archives... [続きを読む]
» アルゴリズムパズル（リンクリスト）の解答編
- 2005年11月16日 23:52
- from 諸悪の根源は物理的
アクセス数が通常の2倍以上になっている。数日前のエントリー「アルゴリズムパズル（リンクリスト）」が大人気だ。既にトラックバックも4つほどついていて、解答も明らか... [続きを読む]
質問です。
１パスの処理で出来るのですか？
通りがかりさん、
１パスの処理です。
is BUG ready ? さんのトラックバック記事に詳しく理由が書いてます。それ以上付け加えることはありません。