リンクされたリストにサイクルがあるかどうかをテストするための最適なアルゴリズム

StackOverflow https://stackoverflow.com/questions/34249

質問

リンクされたリストに循環があるかどうかを判断するための最良の (停止) アルゴリズムは何ですか?

[編集] 時間と空間の両方に対する漸近的な複雑さの分析は、答えをよりよく比較できるようにするのが良いでしょう。

[編集]元の質問は、出次数 > 1 のノードに対処するものではありませんでしたが、それについての話があります。この質問は、「有向グラフ内のサイクルを検出するための最良のアルゴリズム」に近いものです。

役に立ちましたか？

解決

リスト内を反復する 2 つのポインターを用意します。一方を他方の 2 倍の速度で反復させ、各ステップでの位置を比較します。私の頭の上では、次のようなことが考えられます。

node* tortoise(begin), * hare(begin);
while(hare = hare->next)
{
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    hare = hare->next;
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    tortoise = tortoise->next;
}

O(n)、これはできる限り良いことです。

他のヒント

前提条件:リストのサイズを追跡します (ノードが追加または削除されるたびにサイズを更新します)。

ループ検出:

  1. リストのサイズを移動するときにカウンターを保持します。

  2. カウンタがリスト サイズを超える場合、サイクルが発生する可能性があります。

複雑：の上）

注記：カウンタとリスト サイズの比較、およびリスト サイズの更新操作はスレッドセーフにする必要があります。

2 つのポインター *p と *q を取得し、両方のポインターを使用してリンク リスト "LL" の走査を開始します。

1) ポインタ p は毎回前のノードを削除し、次のノードを指します。

2) ポインタ q は毎回順方向のみに進みます。

条件：

1) ポインタ p は null を指し、q は何らかのノードを指します。ループが存在します

2) 両方のポインタが null を指しています。ループはありません

ハッシュ テーブルを使用して、すでに表示されているノードを保存するのはどうですか (リストの先頭から順番に表示します)。実際には、O(N) に近い値を達成できます。

それ以外の場合、ハッシュ テーブルの代わりにソートされたヒープを使用すると、O(N log(N)) が達成されます。

ただ反復する以外に方法はあるのだろうか - 先に進むにつれて配列にデータを設定し、現在のノードがすでに配列に存在するかどうかを確認する...

コンラート・ルドルフのアルゴリズムは、サイクルが始まりを指していないと機能しません。次のリストでは、無限ループになります。1→2→3→2。

DrPizza のアルゴリズムは間違いなく最適な方法です。

この場合、OysterD のコードが最速の解決策になります (頂点カラーリング)。

それは本当に驚きます。私のソリューションでは、リストを介して最大 2 つのパスを作成し (最後のノードが最後から 2 番目のロードにリンクされている場合)、一般的なケース (ループなし) では 1 つのパスのみを作成します。ハッシュやメモリ割り当てなどは行われません。

この場合、OysterD のコードが最速の解決策になります (頂点カラーリング)。

それは本当に驚きます。私のソリューションでは、リストを介して最大 2 つのパスを作成し (最後のノードが最後から 2 番目のロードにリンクされている場合)、一般的なケース (ループなし) では 1 つのパスのみを作成します。ハッシュやメモリ割り当てなどは行われません。

はい。定式化が完璧ではないことに気づき、修正しました。私は今でも、賢いハッシュを使えばほんの少しだけ速く実行できるかもしれないと信じています。私はあなたのアルゴリズムを信じます は 最善の解決策ですが。

私の要点を強調しておきます。Vertec カラーリングは、最新のガベージ コレクターによって依存関係のサイクルを検出するために使用されるため、非常に現実的な使用例があります。彼らは主にビットフラグを使用して色付けを実行します。

これを確認するには、すべてのノードにアクセスする必要があります。これは再帰的に行うことができます。すでに訪問したノードへの訪問を停止するには、「すでに訪問済み」というフラグが必要です。もちろん、これではループが発生しません。したがって、ビットフラグの代わりに数値を使用します。1から始めてください。接続されているノードを確認し、これらを 2 としてマークし、ネットワークがカバーされるまで繰り返します。ノードをチェックするときに、現在のノードより 1 つ以上小さいノードが見つかった場合は、サイクルが存在します。サイクル長は差によって与えられます。

リストの先頭で 2 つのポインタが初期化されます。1 つのポインタは各ステップで 1 回前進し、もう 1 つのポインタは各ステップで 2 回前進します。高速なポインタが低速なポインタと再び出会うと、リスト内にループが発生します。それ以外の場合、より速い方がリストの最後に到達した場合、ループは発生しません。

以下のサンプル コードは、このソリューションに従って実装されています。より速いポインタは pFast、より遅いポインタは pSlow です。

bool HasLoop(ListNode* pHead)
{
    if(pHead == NULL)
        return false;


    ListNode* pSlow = pHead->m_pNext;
    if(pSlow == NULL)
        return false;


    ListNode* pFast = pSlow->m_pNext;
    while(pFast != NULL && pSlow != NULL)
    {
        if(pFast == pSlow)
            return true;


        pSlow = pSlow->m_pNext;


        pFast = pFast->m_pNext;
        if(pFast != NULL)
            pFast = pFast->m_pNext;
    }


    return false;
}

このソリューションは次の場所で入手できます 私のブログ. 。ブログではさらに別の問題が議論されています。リスト内にサイクル/ループがある場合のエントリノードは何ですか?

「ハック」ソリューション (C/C++ で動作するはずです):

  • リストを走査し、次の最後のビットを設定します。 next 1へのポインタ。
  • フラグが設定されたポインタを持つ要素が見つかった場合は、true とサイクルの最初の要素を返します。
  • 戻る前に、ポインターをリセットして戻します。ただし、フラグ付きポインターでも逆参照は機能すると思います。

時間計算量は 2n です。一時変数は使用していないようです。

これは、ハッシュ テーブル (実際には単なるリスト) を使用してポインタ アドレスを保存する解決策です。 

def hash_cycle(node):
    hashl=[]
    while(node):
        if node in hashl:
            return True
        else:
            hashl.append(node)
            node=node.next
    return False

def has_cycle(head):カウンタ = set()

while head is not None:
    if head in counter:
        return True
    else:
        counter.add(head)
        head = head.next
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top