SORU
18 NİSAN 2010, Pazar


Nasıl bağlantılı liste bir döngü algılamak için?

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:

alt text

CEVAP
18 NİSAN 2010, Pazar


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

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • MyTiredBones

    MyTiredBones

    2 Temmuz 2013
  • SVB International

    SVB Internat

    29 EKİM 2011
  • WestsideMrArO

    WestsideMrAr

    6 EKİM 2010