44

リストをトラバースするために2つの変数のみを使用して、リンクされたリストがループするかどうかを見つけるアルゴリズムを知っている人はいますか? オブジェクトのリンクされたリストがあるとします。オブジェクトの種類は関係ありません。1 つの変数にリンクされたリストの先頭へのポインターがあり、リストを走査するための別の変数が 1 つだけ与えられます。

したがって、私の計画は、ポインター値を比較して、同じポインターがあるかどうかを確認することです。リストのサイズは有限ですが、巨大になる可能性があります。両方の変数を先頭に設定してから、他の変数でリストをトラバースし、他の変数と等しいかどうかを常に確認できますが、ループにヒットすると、ループから抜け出すことはできません。リストをトラバースしてポインター値を比較する速度が異なることに関係していると思います。何かご意見は？

4

7 に答える 7

47

Floyd's Cycle-Finding Algorithm 別名Theを使用することをお勧めしTortoise and the Hare Algorithmます。O(n) の複雑さがあり、要件に合っていると思います。

コード例:

function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

ウィキペディアの詳細:フロイドのサイクル発見アルゴリズム.

于 2009-01-30T08:01:32.840 に答える
17

Turtle and Rabbitアルゴリズムを使用できます。

ウィキペディアにも説明があり、「フロイドのサイクル発見アルゴリズム」または「カメとウサギ」と呼ばれています。

于 2009-01-30T07:55:17.440 に答える
9

絶対。解決策の 1 つは、両方のポインターを使用してリストをトラバースすることです。一方は他方の 2 倍の速度で移動します。

リスト内の任意の場所を指す「遅い」および「速い」ポインターから始めます。トラバーサル ループを実行します。いつでも「高速」ポインターが低速ポインターと一致するようになると、循環リンクリストになります。

int *head = list.GetHead();
if (head != null) {
    int *fastPtr = head;
    int *slowPtr = head;

    bool isCircular = true;

    do 
    {
        if (fastPtr->Next == null || fastPtr->Next->Next == null) //List end found
        {
            isCircular = false;
            break;
        }

        fastPtr = fastPtr->Next->Next;
        slowPtr = slowPtr->Next;
    } while (fastPtr != slowPtr);

    //Do whatever you want with the 'isCircular' flag here
}
于 2009-01-30T07:55:59.280 に答える
3

私はこれを自分で解決しようとしましたが、別の (効率は劣りますが最適な) 解決策を見つけました。

このアイデアは、単方向リンク リストを線形時間で反転することに基づいています。これは、リストを反復処理する各ステップで 2 つのスワップを実行することで実行できます。q が前の要素 (最初は null) で p が現在の要素である場合、swap(q,p->next) swap(p,q) はリンクを逆にして、2 つのポインターを同時に進めます。XOR を使用してスワップを実行すると、3 番目のメモリ ロケーションを使用する必要がなくなります。

リストにサイクルがある場合、反復中のある時点で、ポインターが既に変更されているノードに到達します。どのノードかはわかりませんが、いくつかの要素を 2 回交換して反復を続けると、再びリストの先頭に到達します。

リストを 2 回反転すると、リストは結果として変更されず、リストの元の先頭に到達したかどうかに基づいて、循環があったかどうかがわかります。

于 2009-05-05T17:52:17.520 に答える
2 
int isListCircular(ListNode* head){
    if(head==NULL)
        return 0;
    ListNode *fast=head, *slow=head;
    while(fast && fast->next){
        if(fast->next->next==slow)
            return 1;
        fast=fast->next->next;
        slow=slow->next;
    }
    return 0;
}
于 2012-05-09T20:21:18.940 に答える
1 
boolean findCircular(Node *head)
{
    Node *slower, * faster;
    slower = head;
    faster = head->next;
    while(true) {
        if ( !faster || !faster->next)
            return false;
        else if (faster == slower || faster->next == slower)
            return true;
        else
            faster = faster->next->next;
    }
}
于 2015-09-03T14:59:34.923 に答える