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

Question

サイズがわからない循環リンクリストの最後のノードを見つける方法最後のノードはリンクされたリストの最初のノードを除く他のノードを指していますか？

Answer 1

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

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

Answer 2

あなたが最後かどうかを知らせるリストのノードにパラメータを追加することはできますか？私はそれが問題ではないと思う。

それ以外の場合は、すでにvistedしているノードを覚えておくことができます。次のノードが既に訪問されている場合、あなたは最後にいる。

Answer 3

奇妙なリスト...なぜこのようなものが必要でしょうか？しかし、とにかく...

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

訪問したノードを追跡するには、何らかの方法が必要です。ブール値フラグを各ノードに追加するか、または高速挿入と検索（例：ハッシュセット）を伴う何らかの種類のセットデータ型を使用します。このために使用することができる

Answer 4

1つのアルゴリズムは、フロイド・サイクル・アルゴリズムは、リストの最後の要素を与えることはありませんthis question.

Answer 5

を参照してください。またFloyd cycle algorithm.

です。それはサイクルがあるかどうかだけを伝えます。

最後の定義の定義は、最初のものから順番にスキャンを実行している間に、その前のすべての要素と最後の要素が表示されていないことです（ポインタ値）。最後のものは、この順次スキャンで既に見られた最初の要素になります。

簡単な解決策は訪問済みの要素にフラグを立てて、既に見られた要素が容易に検出されるようにすることです。フラグは、侵入的であってもよく、すなわち、要素内のビットを変更することによって、またはポインタ値を格納するためにハッシュテーブルを使用することによって外部から変更することができる。

要素がすでに訪問されているかどうかをテストする必要があるため、私は別の解決策を見ません。

Answer 6

私はこの問題を解決するためにフロイドのアルゴリズムを使用する方法について詳しく説明することができますが、私は一歩

1. についての説明は、2つのポインタが、ポインタ1は1の割合で起こって、リンクリストをトラバース持って理解していません2つ目のノードは2ノードの割合で実行されます
2. ポインタが一致すると、サイクルが終了し、ポインタ1がサイクルの最後に到達するまでにある程度距離があります（ポインタ1が到達していないサイクルが距離dでポインタ2が1の速度の2倍になると、ポインタ1はポインタ1が一度それを行う前にサイクルを2回ループするからです）
3. したがって、ポインタ1がサイクルを完全に横断する前に満たされているので、このミーティングポイントはサイクル内の開始ノードからk個のノードまでのd個のノードです（pos = d + k）
4. ポインタ1をposition 0に設定し、両方の点を再び開始します（反復ごとに1つのノードの率が同じである）が、サイクルの開始時に一致します。
5. 我々はサイクルの開始を知っているので、ステップ4が真である理由の端を見つけること

簡単です私は完全には理解していないが、私は友人が私に解決策を説明しました。