結城浩のはてなブログ

ふと思いついたことをパタパタと書いてます。

単方向linked listの循環参照判定をO(n)で行なう

やねうらおさんの単方向linked listの循環参照判定をO(n)で行なうの問題を見て、結城も考えてみました。私が思いついた解答もやねうらおさんのものと同じだったので、ちょっとうれしかったり。しかし『エキスパートCプログラミング』に載っていたという解答を見て、そのシンプルさにショックを受けたり。楽しいひと時を過ごしました(加筆:もう一度やねうらおさんの解答を読み返して、結城が考えていた方法とは違っていることに気づきました。私の方法は間違いでした。しょぼーん)。
ちなみに「ロウ法」を思い出しました。「ロウ法」というのは大きな合成数の素因数を発見するためのヒューリスティックな方法のこと(必ず見つかるとは限らない)。尻尾の部分とループの部分を組み合わせるとギリシア文字のρの形をしているからこの名前がついています。