c - サイズが不明で、最後のノードがリンクリストの最初のノードを除く他のノードを指している循環リンクリストの最後のノードを見つける

Question

サイズがわからない循環リンクリストの最後のノードを見つけるにはどうすればよいですか?最後のノードは、リンクリストの最初のノード以外の他のノードを指していますか?

score 4 · Accepted Answer

これに使用できる 1 つのアルゴリズムは、フロイドサイクルアルゴリズムです。

score 3 · Accepted Answer

定義により、ノードが循環リンクリストの最初のノードを指していない場合、
それは最後のノードではありません。

ここで詳しく説明できますか？

score 2 · Accepted Answer

変なリスト…どうしてこんなものが必要になるの？とにかく...

すべてのノードを単純に反復し、次のノードが既に訪れたノードになるとすぐに停止できます。現在のノードが答えになります。

どのノードが訪問されたかを追跡する何らかの方法が必要です。各ノードにブール値フラグを追加するか、高速な挿入とルックアップを備えたある種のセットデータ型を使用します (例: ハッシュセット)。

score 0 · Accepted Answer

フロイドサイクルアルゴリズムは、リストの最後の要素を提供しません。サイクルがあるかどうかだけがわかります。

最後の要素の定義は、最初の要素から始まる順次スキャンでリストをトラバースしている間、その前のすべての要素と最後の要素が前に表示されないことです (ポインター値)。最後の要素は、このシーケンシャルスキャンで既に確認された最初の要素になります。

簡単な解決策は、訪問した要素にフラグを付けて、既に見た要素を簡単に検出できるようにすることです。フラグは、要素内のビットを変更することによって、またはポインター値を格納するためにハッシュテーブルを使用することによって外部的に侵入する可能性があります。

要素が既にアクセスされているかどうかをテストできるようにする必要があるため、別の解決策はありません。

score 0 · Accepted Answer

リストのノードにパラメーターを追加して、最後にあるかどうかを教えてくれるでしょうか？問題ないと思います。

それ以外の場合は、既にアクセスしたノードを思い出すことができます。次のノードがすでに訪問されている場合、あなたは終わりです。

score 0 · Accepted Answer

フロイドのアルゴリズムを使用してこの問題を解決する方法について詳しく説明できますが、1 つのステップの説明がわかりません

2 つのポインターがリンクされたリストをトラバースし、ポインター 1 は反復ごとに 1 ノードの速度で移動し、2 番目のポインターは 2 ノードの速度で移動します。
ポインターが出会うと、サイクル内にあり、ポインター 1 がサイクルの終わりに到達する前に、ある程度の距離があります (サイクルが距離 d で、ポインター 2 が 2 倍の速度で移動している場合、ポインター 1 が到達していないことがわかります。速度が 1 の場合、ポインター 1 はサイクルを 2 回ループしてから、ポインター 1 が 1 回ループします)
したがって、ポインタ 1 がサイクルを完全に横断する前にそれらが出会ったため、会合点は開始から d ノードであり、サイクル内の k ノードであることがわかります (pos = d + k)
ポインター 1 を位置 0 に設定し、両方のポイントを再び開始すると (ただし、反復ごとに 1 ノードという同じレートで)、それらはサイクルの開始時に一致します。
サイクルの始まりを知っているので、終わりを見つけるのは簡単です

ステップ 4 が正しい理由がよくわかりませんが、友人に解決策を説明してもらいました。

6 に答える 6