Java bağlı bir liste yapısı var. Düğümler oluşuyor:

class Node {
    Node next;
    // some user data
}

ve her Düğüm sonraki düğüm, bir sonraki boş olan son Düğüm hariç işaret eder. Listeyi daha önce gelen bir döngü yani son Düğüm yerine boş olması, listedeki düğümleri için bir başvuru içeren bir olasılık olduğunu söylüyorlar.

Yazmanın en iyi yolu nedir

boolean hasLoop(Node first)

verilen Düğüm döngü ile listenin ilk ve false true dönecekti yoksa? Nasıl uzayda sabit bir miktar ve zaman makul miktarda alır diye yazar mısın?

Burada bir döngü ile bir liste gibi görünüyor ne bir resim:

Floyd's cycle-finding algorithm kullanımı olarak da yapabilirsinizkaplumbağa ve tavşan algoritması.

Fikir listesi için iki başvuru var ve onları taşımak içinfarklı hızlarda. Bir ileri 1 düğüm ile hareket 2 diğer düğümler.

• Eğer bir bağlantılı liste bir döngü varsa kesinliklekarşılamak.
• Başka birini iki referansları(9**) null olacak.

Java fonksiyonu algoritması uygulama:

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;
    }
}