ytqwerty https://blog.hatena.ne.jp/ytqwerty/ Note https://ytqwerty.hatenadiary.org/ http://d.hatena.ne.jp/ladybug/20051116#p1 O(n^2)ならできそうなんだけどなぁ…。 そうか！走査を終えたノードを解放していけば、循環でアクセス違反が起きるので判別できるぞ！ …ごめんなさい。 マーキング無しということは、マーキング同様の手法も無しということらしいので、n個の配列とかも無し、スタックを同様に使うのも無し…ううむ。 つまるところ、個数nがわかっていれば、適当にあっちこっち巡回してn回以上リンクを辿っていればそれは循環とわかる、が、nがわからないので、nを求めるためにはやはりマーキングがいるよね、という話らしい。なのでこの手の手法は使えない… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fytqwerty.hatenadiary.org%2Fentry%2F20051116%2Fp1" title="循環参照した短方向リンクリストを O(n) で検出する気持ちさえあれば - Note" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2005-11-16 00:00:00 rich https://ytqwerty.hatenadiary.org/entry/20051116/p1 1.0 100%