この質問は、2 つのリンクされたリストの交点を見つけることとは少し異なります。
ループのあるリンクリストを考えてみましょう: A - B - C - D - E - F - C.
ノードAが関数への入力である場合、それは を返す必要がありCます。
何と呼ぶべきかわからないので、質問に見られるようにCループノードという用語を使用しました。CO(n 2 ) 項は明白に見えますが、複雑さの少ないループノードを見つける方法はありますか?
ハッシュ テーブル / O(n) の余分なスペースは許可されていません。
フロイドのサイクル発見アルゴリズムは最も単純なものであり、誰もが大学で学ぶものであるため、多くの場合「標準的な答え」です (おそらく、単純でエレガントで洞察に富んでいるため)。
また、ランタイムは改善できないと主張されることもよくありますが、そうではありません。大きな問題は改善できない可能性がありますが、それは最悪の場合の漸近的な動作について何かを教えてくれるだけです。Brent のアルゴリズムは、一定量のスペースを使用しながら、実際にはより高速です。Gosper の Loop Detection や Sedgewick、Szymanski、Yao のアルゴリズム、またはk-stacks アルゴリズムなど、特定の (低いが理論的には一定ではない) スペースを使用するアルゴリズムは他にもあります。実際には、リンクされたリストの実際の実装では、ポインターが固定サイズになるため、スペースの量は依然として一定です。たとえば、32 ビット ポインターの場合、Gosper のループ検出では 33 ワードのスペースが使用されます (さらに、何をカウントするかによって、さらに 2、3 ワードが余分に使用されます)。
Floyd のアルゴリズムは優れていますが、必ずしも The Answer (tm)とは限りません。選択とトレードオフが必要です。