Röportajda bu soru soruldu: "Nasıl bir bağlantı listesinde döngü algılamak için?", Ama bu hemen spiker sordu nasıl bağlantılı liste döngü kaldırırım bana çözdüm. Ben arandı.

Bu çözmek için nasıl herhangi bir tavsiye, sahte kod veya yöntem tanımı olabilir mi?

Java altında bu soru etiketli Var Java içim rahat.

Örneğin bu bağlı liste bir döngü var

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

Bu sorunun iki bölümü vardır:

1. Eğer listede bir döngü varsa tespit
2. Döngü başlangıcı belirlemek

Bir kere nereden döngü başlar, kolay tanımlamak son öğe listesinde bu yana öğe listesi aşağıdaki başlangıç döngü sonu geri işaret Başlat döngü. O zaman önemsiz ayarlamak için bir sonraki işaretçi/referans bu öğe için null doğru döngüsel bir bağlantı listesi (dairesel bağlantılı liste nerede son elemanları puan geri - bu belirli bir örnek döngüsel listeler).

1. Farklı hızlarda hareket eden başvurular/iki işaretçileri kullanarak karıştırmak gibi Floyd's cycle detect algorithm, also called the tortoise and hare algorithm döngü algılama bir yoludur. Eğer bir döngü varsa, iki işaretçiler (p1 p2) adımları sınırlı sayıda sonra aynı öğeye işaret eder. İlginçtir ki, onlar karşılamak unsuru olacağını kanıtladıbu başlangıç için aynı mesafededöngü(traverse aynı, ileri yönde listesi devam) döngü başlangıcıbaşliste. Yani, eğer doğrusal parça listesi k elemanlar, iki işaretçiler karşılayacak döngünün içinde uzunluğu m m-k baştan döngü veya k elementler için 'son' loop (tabii ki, bu bir döngü yani 'end' - 'başlangıç' bir kez daha). Ve bu bize döngünün başlangıcını bulmak için bir yol verir:

2. Bir kez bir döngü algılanması, izin p2 kalır işaret, eleman nerede döngü için yukarıdaki adım sonlandırıldı ama reset p1 diye işaret geri kafa listesini. Şimdi, bir anda, her bir işaretçi bir öğe taşıyın. p2 döngünün başlamasından bu yana, döngü devam edecek. k adımları () listenin en başından döngünün başlangıç uzaklığı eşit sonra, p1 p2 tekrar bir araya gelecek. Bu döngünün başlangıç için bir referans verebilir.

3. Şimdi kolay p1 (ya da p2) döngü başlangıç öğesi üzerine gelin ve p1 sona kadar döngü traverse başlangıç öğesi geri işaret koyarım. Bu noktada p1 'son' bir öğe listesi ve bunu bir sonraki işaretçi 20 ** için ayarlanabilir. başvuran

Burada hızlı ve kirli bazı Java kodu Nodenext başvuruda bulunduğu Node s bağlantılı bir listesi varsayarsak. Bu optimize edilmiş olabilir ama temel fikir verebilir:

Node slow, fast, start;
fast = slow = head;

//PART I - Detect if a loop exists
while (true)
{
    // fast will always fall off the end of the list if it is linear
    if (fast == null || fast.next == null)
    {
        // no loop
        return;
    }
    else if (fast == slow || fast.next == slow)
    {
        // detected a loop
        break;
    }
    else
    {
        fast = fast.next.next; // move 2 nodes at at time
        slow = slow.next; // move 1 node at a time
    }
}

//PART II - Identify the node that is the start of the loop
fast = head; //reset one of the references to head of list

//until both the references are one short of the common element which is the start of the loop
while(fast.next != slow.next) 
{
    fast = fast.next;
    slow = slow.next;
}

start = fast.next;

//PART III - Eliminate the loop by setting the 'next' pointer 
//of the last element to null
fast = start;
while(fast.next != start)
{
    fast = fast.next;
}

fast.next = null; //break the loop

This explanation neden Bölüm II geride yardımcı olabilir:

Döngü uzunluğu M olduğunu varsayalım, ve geri kalan uzunluğu bağlantılı liste L. hadi anlamaya. pozisyon döngüsü içinde zaman nedir /t2 t1 ilk tanışma?

Döngüsünün ilk düğüm atar. pozisyon bağlantıları aşağıdaki 0, pozisyon 1, 2,..., M-1'e kadar. ( döngüsü, içeri girdiğimizde, bizim geçerli konum (walk_length) mod M, değil mi?) T1/t2 ilk buluş sanırım p konumu, yolculuk süresi vardır aynı, (L k1*M p)/v = (L k2*M p) 2v/ bazı k1

Eğer t1 başlarsanız sonucuna varılıyor yani p, t2 baş ve hareket başlangıç aynı hız, daha sonra karşılamak için hibe edecek pozisyon 0, ilk düğümünü döngüsü. QED.

Daha fazla başvuru:

• http://www.quora.com/How-does-Floyds-cycle-finding-algorithm-work
• Explain how finding cycle start node in cycle linked list work?
• Proof of detecting the start of cycle in linked list
• Hristo's answer to this question on this page da bir görüşme kitaptan bir açıklama tırnak