c# - C# を使用した LinkedList でのループ検出

Question

インタビューの質問では、「ループの存在を検出するアルゴリズムを実装してください。」. たとえば、リンクされたリストには次のようなループがあります。

0--->1---->2---->3---->4---->5---->6
                 ▲                 |
                 |                 ▼
                11<—-22<—-12<—-9<—-8

Floyd のサイクル検出を使用すると、高速 & 低速ポインターを使用することでこの問題を解決できます。じゃあ比較してみようかな

を。リンクのノード値、つまり

if (fast.data == slow.data) 
    break;

fast と slow はタイプですLink

class Link
{
    int IData {get; set;}
    Link Next {get; set;}
}

また

b. それらは同じ参照を指していますか、つまりif (fast == slow)

ありがとう。

Answer 1

ノード自体のみを比較する必要があります。結局のところ、実際にはサイクルを持たずに、繰り返されるデータを含むリンクされたリストを持つことは合理的です。

リンクではなくノードとも呼びます。リンクは単純に、あるノードから次または前のノードへの参照です。特に、リンクに関連付けられたデータはなく、ノードにのみ関連付けられています。