BaruLog × ばるろぐ

12345678910111213141516171819202122232425262728293031


単方向リストのループをO(N)で検出するアルゴリズム

投稿者:barukichi
投稿日時:2006-01-08 - 04:04:39
カテゴリー:Bookmark - トラックバック(No Trackbacks)
タグ:
Alternative 笑門来福 - この問題あなたは解けますか?

『【問題】 単方向リストがある。ノード数を n とするが、n の値は分からない。リスト中にループ(循環参照)が存在するか否かを O(n) で判定するアルゴリズムを示せ。ただし、単純にポインタが指したノード全てにマーキングをしておいて、新しいノードに移るたびにマーキングされているかを調べることで判定することは禁じ手とする

こーいうの大好きw
きゃっきゃ言いながら考えちゃう(言わないけど)w

「n の値は分からない」ってのと「ただし、単純に~~」って条件がキツい^^

で、答えが分からないwww

「マーキングによるループ検出が禁じ手」って部分がよく分からないってのもある。「単純なマーキングによるアルゴリズムは面白くないから却下」なのか、それともマーキングに類するもの全てが禁じ手なのか。後者だといよいよO(N)の解法の想像がつかないから、多分というか、きっと前者の筈だが。んーー。。。

でも考えてみることが大事だな^^


色々考えたけどギブアップw
で、このログエントリーにコメントされてたサイトを見て納得。

作業日誌(みすみロボット研究所) - アルゴリズム問題、解けるかな?

『逆方向への単方向リストに変換したときに、変換前のHead が指し示す要素のNextの値がNULLではない場合、循環参照がある』

なるほどー^^

これが正解かどうかは分からないけど、実際に図を書いて手順を追ってみて納得はできた。
自分もまだまだ頭が固いな^^;

Comments

オニギリ・ジョー wrote:

循環があるかを判定する問題なのに、循環部分とそうでない部分に操作を分けているように見えるのですが。それにリストは都合のいい順番であるとは限らないし、ノードは1vs1だけとも限りませんよね?
2017-05-16 18:06:04

Add Comments

[スパム対策] コメントの送信はJavaScriptを利用できることが条件です %20%3c%61%20%69%64%3d%22%6e%75%63%6c%65%75%73%5f%63%66%22%3e%3c%2f%61%3e %3c%66%6f%72%6d%20%6d%65%74%68%6f%64%3d%22%70%6f%73%74%22%20%61%63%74%69%6f%6e%3d%22%23%6e%75%63%6c%65%75%73%5f%63%66%22%3e %09%3c%64%69%76%20%63%6c%61%73%73%3d%22%63%6f%6d%6d%65%6e%74%66%6f%72%6d%22%3e %3c%69%6e%70%75%74%20%74%79%70%65%3d%22%68%69%64%64%65%6e%22%20%6e%61%6d%65%3d%22%61%63%74%69%6f%6e%22%20%76%61%6c%75%65%3d%22%61%64%64%63%6f%6d%6d%65%6e%74%22%20%2f%3e %3c%69%6e%70%75%74%20%74%79%70%65%3d%22%68%69%64%64%65%6e%22%20%6e%61%6d%65%3d%22%75%72%6c%22%20%76%61%6c%75%65%3d%22%62%61%72%75%6c%6f%67%2e%70%68%70%3f%69%74%65%6d%69%64%3d%34%36%30%22%20%2f%3e %3c%69%6e%70%75%74%20%74%79%70%65%3d%22%68%69%64%64%65%6e%22%20%6e%61%6d%65%3d%22%69%74%65%6d%69%64%22%20%76%61%6c%75%65%3d%22%34%36%30%22%20%2f%3e %09%09 %09%09%3c%6c%61%62%65%6c%20%66%6f%72%3d%22%6e%75%63%6c%65%75%73%5f%63%66%5f%62%6f%64%79%22%3eコメント%3a%3c%2f%6c%61%62%65%6c%3e %09%09%3c%74%65%78%74%61%72%65%61%20%6e%61%6d%65%3d%22%62%6f%64%79%22%20%63%6c%61%73%73%3d%22%66%6f%72%6d%66%69%65%6c%64%22%20%63%6f%6c%73%3d%22%34%30%22%20%72%6f%77%73%3d%22%31%30%22%20%69%64%3d%22%6e%75%63%6c%65%75%73%5f%63%66%5f%62%6f%64%79%22%3e%3c%2f%74%65%78%74%61%72%65%61%3e %09%09%3c%6c%61%62%65%6c%20%66%6f%72%3d%22%6e%75%63%6c%65%75%73%5f%63%66%5f%6e%61%6d%65%22%3eお名前%3a%3c%2f%6c%61%62%65%6c%3e %09%09%3c%69%6e%70%75%74%20%6e%61%6d%65%3d%22%75%73%65%72%22%20%73%69%7a%65%3d%22%34%30%22%20%6d%61%78%6c%65%6e%67%74%68%3d%22%34%30%22%20%76%61%6c%75%65%3d%22%22%20%63%6c%61%73%73%3d%22%66%6f%72%6d%66%69%65%6c%64%22%20%69%64%3d%22%6e%75%63%6c%65%75%73%5f%63%66%5f%6e%61%6d%65%22%20%2f%3e %09%09%3c%6c%61%62%65%6c%20%66%6f%72%3d%22%6e%75%63%6c%65%75%73%5f%63%66%5f%6d%61%69%6c%22%3eウェブサイト%3a%3c%2f%6c%61%62%65%6c%3e %09%09%3c%69%6e%70%75%74%20%6e%61%6d%65%3d%22%75%73%65%72%69%64%22%20%73%69%7a%65%3d%22%34%30%22%20%6d%61%78%6c%65%6e%67%74%68%3d%22%36%30%22%20%76%61%6c%75%65%3d%22%22%20%63%6c%61%73%73%3d%22%66%6f%72%6d%66%69%65%6c%64%22%20%69%64%3d%22%6e%75%63%6c%65%75%73%5f%63%66%5f%6d%61%69%6c%22%20%2f%3e %09%09%3c%6c%61%62%65%6c%20%66%6f%72%3d%22%6e%75%63%6c%65%75%73%5f%63%66%5f%65%6d%61%69%6c%22%3eメール%3a%3c%2f%6c%61%62%65%6c%3e %09%09%3c%69%6e%70%75%74%20%6e%61%6d%65%3d%22%65%6d%61%69%6c%22%20%73%69%7a%65%3d%22%34%30%22%20%6d%61%78%6c%65%6e%67%74%68%3d%22%31%30%30%22%20%76%61%6c%75%65%3d%22%22%20%63%6c%61%73%73%3d%22%66%6f%72%6d%66%69%65%6c%64%22%20%69%64%3d%22%6e%75%63%6c%65%75%73%5f%63%66%5f%65%6d%61%69%6c%22%20%2f%3e %09%09 %09%09%3c%69%6e%70%75%74%20%74%79%70%65%3d%22%63%68%65%63%6b%62%6f%78%22%20%76%61%6c%75%65%3d%22%31%22%20%6e%61%6d%65%3d%22%72%65%6d%65%6d%62%65%72%22%20%69%64%3d%22%6e%75%63%6c%65%75%73%5f%63%66%5f%72%65%6d%65%6d%62%65%72%22%20%20%2f%3e %09%09%3c%6c%61%62%65%6c%20%66%6f%72%3d%22%6e%75%63%6c%65%75%73%5f%63%66%5f%72%65%6d%65%6d%62%65%72%22%3e情報を記憶しておく%3c%2f%6c%61%62%65%6c%3e %09%09%3c%69%6e%70%75%74%20%74%79%70%65%3d%22%73%75%62%6d%69%74%22%20%61%6c%74%3d%22コメントを追加%22%20%76%61%6c%75%65%3d%22コメントを追加%22%20%63%6c%61%73%73%3d%22%66%6f%72%6d%62%75%74%74%6f%6e%22%20%2f%3e %09%3c%2f%64%69%76%3e %3c%2f%66%6f%72%6d%3e %20