-1

次のように、タートルとウサギのソリューションを使用して見つけたリンクリストのループを見つける必要があります

boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either.
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list.

    while(true) {

        slow = slow.next;          // 1 hop.

        if(fast.next != null)
            fast = fast.next.next; // 2 hops.
        else
            return false;          // next node null => no loop.

        if(slow == null || fast == null) // if either hits null..no loop.
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop.
            return true;
    }
}

そして今、私の問題は、ループの開始を検出する方法と、リストのサイズを大きくしたかのようにプログラムの複雑さを計算する方法です。ポインターが出会うポイントは、リストのサイズの割合で増加しません。

4

2 に答える 2

1

コーディングインタビューのクラックから：

例えとして、2 人がトラックを走り回り、一方が他方の 2 倍の速さで走っていると想像してください。同じ場所から出発した場合、次に会うのはいつですか? 彼らは次のラップの開始時に次に会います。

ここで、Fast Runner が n ステップのラップで k メートルの先行スタートを切ったとします。彼らが次に会うのはいつですか？彼らは次のラップの開始前に k メートルに会います。(理由は? Fast Runner は、ヘッド スタートを含めて k + 2(n - k) ステップを実行し、Slow Runner は n - k ステップを実行します。両方とも、ループの開始前に k ステップになります。)

さて、問題に戻ると、Fast Runner (n2) と Slow Runner (n1) が循環リンク リストの周りを移動している場合、n1 がループに入ると、n2 は有利なスタートを切ります。具体的には、ループの前のノード数である k のヘッド スタートがあります。n2 は k 個のノードの先頭にあるため、n1 と n2 はループの開始前に k 個のノードに遭遇します。

したがって、次のことがわかりました。

  1. ヘッドは (定義により) LoopStart からの k ノードです。
  2. n1 および n2 の MeetingPoint は、LoopStart からの k ノードです（上記のとおり）。

したがって、n1 を Head に戻し、n2 を MeetingPoint に保ち、両方を同じペースで移動すると、LoopStart で合流します。

LinkedListNode FindBeginning(LinkedListNode head) 
{
    LinkedListNode n1 = head;
    LinkedListNode n2 = head;
    // Find meeting point
    while (n2.next != null) 
    {
        n1 = n1.next;
        n2 = n2.next.next;
        if (n1 == n2) 
        {
            break;
        }
    }

     // Error check - there is no meeting point, and therefore no loop
     if (n2.next == null) 
     {
        return null;
     }

    /* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps
    /* from the Loop Start. If they move at the same pace, they must
    * meet at Loop Start. */
    n1 = head;
    while (n1 != n2) 
    {
        n1 = n1.next;
        n2 = n2.next;
    }
    // Now n2 points to the start of the loop.
    return n2;
}
于 2013-10-19T07:57:56.633 に答える
0

ループがない場合は、Θ(n)少なくともn回数と多くの3/2*n回数ホップするため、コードは実行されます。

ループがある場合、グラフ理論の用語では、最大で の長さのサイクルですn。サイクル間の距離fastとサイクル上の距離はホップごとslowに正確に変化するため、両方がループに入った後、出会うまではほとんどの場合ホップします。どちらも最大ホップ数後にループに入るため、最悪の場合の複雑さが生じます。1nn-12*(n-1) + 2*n ∈ O(n)

[ループの最良のケースの複雑さはO(1)、ループにすぐに入ることができるためです。つまり、一定数のホップの後であり、あまり興味深いものではありません。]

于 2013-10-19T11:48:10.577 に答える