algorithm - リンクリストのループはいつ役に立ちますか？

Question

単一リンクリストにループがあるかどうかを判断することは、一般的なインタビューの質問です。しかし、なぜリンクリストがループとともに存在するのでしょうか。ループ付きのリンクリストはいつ役に立ちますか？

Answer 1

循環リンクリストは、ランダムなイテレータから開始するか、任意の位置に挿入してリスト全体を反復処理する場合に役立ちます。リストの最初または最後を考慮する必要がないため、これらの操作のアルゴリズムが簡素化されます。

Answer 2

たとえば、どの要素をパラメータとして関数に渡すかは重要ではありません。センチネルパターンを使用する場合は、各要素をすべて同じように繰り返します。

Answer 3

Apacheは、循環リンクリストを使用してすべてのフィルターを格納します。

どういうわけか、彼らはそれに派手なマーケティング名（「バケツリレー」）を付けて、それを「主要な革新」と呼んでいます-笑。

Answer 4

循環リンクリストを使用するには、本質的に循環構造であると考えることができます。FIFOの順序で使用および解放されるバッファのプール、ラウンドロビンの順序でタイムシェアリングする必要がある一連のプロセス、またはポリゴンのノード座標を特定の順序で保存するなど。

Answer 5

ここに示されている多くの回答は、完全にループされたリンクリストを考慮しています。

面接の質問は少し異なります。リンクのどこかでループ（部分的である可能性があります）を検出する必要があります

例:(グラフィックが貧弱でごめんなさい）

1-> 2-> 3-> 4-> 5 

          ^ v 

          7 <----- 6

それがどのように起こり得るかに対する答え：リンクの破損。
a）UGC（ユーザー生成コンテンツ）を介して侵入しようとしている人々。悪いデータが出てくる可能性があります。
b）初期段階での設計上の欠陥。

このループ検出は、疑わしいバグを探すためにLinkedListsで行うテストの一部でもあります。

あなたは解決策を求めていませんが、ここにいくつか簡単に説明します。

1. ノードをリスト（JavaではArraylist）にプッシュし続けます。重複を見つけた時間：ループが検出されました
2. タートル＆ヘアアプローチ。Turtleは一度に1つのノードをジャンプします。ウサギ、一度に2匹。ループなら会う
3. トラバースするときにブールフラグを*訪問*して保存します。*true*の遭遇はすべてループです。