- - PR -
アルゴリズムパズル(リンクリスト)
投稿者 | 投稿内容 | ||||
---|---|---|---|---|---|
|
投稿日時: 2005-11-16 15:02
あぁ寝ぼけてました。
循環してたらnはもとまりませんねぇ
cats様、zar様 すばらしい。 最悪は逃げるほうのポインタが1周余計にループ部を多く回ることになりそうですが ばっちり判定できてますね。 感動しました。 | ||||
|
投稿日時: 2005-11-16 15:02
なるほどねぇ。
2つのポインタで追いかけっこですか。 catsさんのソースを私なりに書いてみました。(C#) nullか調べるのはlじゃなくてpですね。pの方が先に進んでますから。
| ||||
|
投稿日時: 2005-11-16 15:06
kanaiです。
ごめんなさい。先ほどのコードはバグがありました。 もう一度出直してきます。 | ||||
|
投稿日時: 2005-11-16 15:32
kanaiです。
再びチャレンジしてみました。 先に投稿したコードと同様、リンクリストはInteger配列で表現し、 添字0の要素がリストの先頭、要素-1はリストの末尾を表すものとします。 list(i)とlist(list(i))の要素を交換してもリンクリストとしては等価で あることに着目し、要素を順次交換していき、末尾にたどり着くか、 それとも同じポインタを指し続けるのかを判定しています。 こんな感じでいかがでしょう?
編集 ・ExchangeMemberに一箇所間違いがあるのを修正 ・確認用に、リンクリストの内容を出力するように変更 ・IsLoopedで引数listをコード中で再利用している箇所をリファクタリング ・コメントを追加 編集2 ・ExchangeMemberで引数listが書き換えられてしまうのを修正 (配列をコピーするコードが美しくないのですが・・・) [ メッセージ編集済み 編集者: kanai 編集日時 2005-11-16 16:07 ] [ メッセージ編集済み 編集者: kanai 編集日時 2005-11-16 17:01 ] | ||||
|
投稿日時: 2005-11-16 15:55
一個思いつきました。
休憩中に考えて細かく検証してないので、自信ありませんが、とりあえず投下してみます。 まず、リストを順方向に辿っていくAがいます。 Aは自分が辿ってきた道筋を、逆向きの単方向リストとして作成していきます。 そして常にAの一個前にいるaと、逆方向のリストを辿っていくBがいます。 Bは、リストの先頭に達したら、Aと同じ位置に戻ります。 で、リストの先頭に達する前にBがAまたはaと出会ったら、 循環参照ハケーン!!(・∀・) 以下、コードだとわかりづらいので一例を図化します。
| ||||
|
投稿日時: 2005-11-16 17:39
なるほどー、確かに出来ますねw | ||||
|
投稿日時: 2005-11-16 19:32
らぶまです。
もう答えは出ていますが、 私も思いついた案を出してみます。 問題文を「リストのノードの内容以外なら変更してよい」 と曲解すれば、 元のリストのノードとノードの間に新しいノードを追加しながら走査する。 nilに達するまでに、追加したノードに出会ったら循環リスト。 ノードにマーキングしているわけではないので、問題文の制約には抵触しないかなと・・ 元のリストは破壊するので、問題の趣旨には反していますが・・・ (後で元に戻す処理を追加すればいいかな)。 ぼのぼのさんの書き方をお借りすると、と思ったらなぜか上手く表示されないので、 ちょっと変更。(8 )→(4 )で循環していると考えて、 丸が追加分,*がカレントのノード コード: -------------------------------------------------------------------------------- (*1)→(2 )→(3 )→(4 )→(5 )→(6 )→(7 )→(8 )→(4 )→... (1 )→(○)→(*2)→(3 )→(4 )→(5 )→(6 )→(7 )→(8 ) (1 )→(○)→(2 )→(○)→(3 )→(○)→(4 )→(○)→(5 )→(○)→(6 )→(○)→(7 )→(○)→(8 )→(○)→(*4)→(○)→... [ メッセージ編集済み 編集者: らぶま 編集日時 2005-11-16 19:35 ] [ メッセージ編集済み 編集者: らぶま 編集日時 2005-11-16 19:35 ] | ||||
|
投稿日時: 2005-11-16 19:39
[code]ですな |