Bagaimana cara mendeteksi loop dalam daftar tertaut?

Katakanlah Anda memiliki struktur daftar tertaut di Jawa. Ini terdiri dari Nodes:

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

dan setiap Node menunjuk ke node berikutnya, kecuali untuk Node terakhir, yang memiliki null untuk selanjutnya. Katakanlah ada kemungkinan bahwa daftar tersebut dapat berisi loop - yaitu Node akhir, daripada memiliki nol, memiliki referensi ke salah satu node dalam daftar yang datang sebelumnya.

Apa cara penulisan terbaik

boolean hasLoop(Node first)

yang akan kembali truejika Node yang diberikan adalah yang pertama dari daftar dengan loop, dan falsesebaliknya? Bagaimana Anda bisa menulis sehingga dibutuhkan ruang yang konstan dan waktu yang masuk akal?

Berikut ini gambaran tampilan daftar dengan lingkaran:

Anda dapat menggunakan algoritme pencarian siklus Floyd , yang juga dikenal sebagai algoritma kura-kura dan kelinci .

Idenya adalah memiliki dua referensi ke daftar dan memindahkannya dengan kecepatan yang berbeda . Pindahkan satu maju dengan 1simpul dan lainnya dengan 2simpul.

• Jika daftar tertaut memiliki loop, mereka pasti akan bertemu.
• Kalau tidak salah satu dari dua referensi (atau mereka next) akan menjadi null.

Fungsi Java mengimplementasikan algoritma:

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

Inilah penyempurnaan dari solusi Cepat / Lambat, yang dengan benar menangani daftar panjang ganjil dan meningkatkan kejelasan.

boolean hasLoop(Node first) {
    Node slow = first;
    Node fast = first;

    while(fast != null && fast.next != null) {
        slow = slow.next;          // 1 hop
        fast = fast.next.next;     // 2 hops 

        if(slow == fast)  // fast caught up to slow, so there is a loop
            return true;
    }
    return false;  // fast reached null, so the list terminates
}

Lebih baik daripada algoritma Floyd

Richard Brent menggambarkan algoritma pendeteksi siklus alternatif , yang mirip seperti kelinci dan kura-kura [Floyd's cycle] kecuali bahwa, simpul lambat di sini tidak bergerak, tetapi kemudian "diteleportasikan" ke posisi simpul cepat di fix interval.

Deskripsi tersedia di sini: http://www.siafoo.net/algorithm/11 Brent mengklaim bahwa algoritmanya 24 hingga 36% lebih cepat daripada algoritme siklus Floyd. O (n) kompleksitas waktu, O (1) kompleksitas ruang.

public static boolean hasLoop(Node root){
    if(root == null) return false;

    Node slow = root, fast = root;
    int taken = 0, limit = 2;

    while (fast.next != null) {
        fast = fast.next;
        taken++;
        if(slow == fast) return true;

        if(taken == limit){
            taken = 0;
            limit <<= 1;    // equivalent to limit *= 2;
            slow = fast;    // teleporting the turtle (to the hare's position) 
        }
    }
    return false;
}

Solusi alternatif untuk Turtle and Rabbit, tidak begitu baik, karena saya sementara mengubah daftar:

Idenya adalah untuk berjalan daftar, dan membalikkannya saat Anda pergi. Kemudian, ketika Anda pertama kali mencapai node yang telah dikunjungi, pointer berikutnya akan menunjuk "mundur", menyebabkan iterasi untuk melanjutkan ke arah firstlagi, di mana ia berakhir.

Node prev = null;
Node cur = first;
while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}
boolean hasCycle = prev == first && first != null && first.next != null;

// reconstruct the list
cur = prev;
prev = null;
while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}

return hasCycle;

Kode uji:

static void assertSameOrder(Node[] nodes) {
    for (int i = 0; i < nodes.length - 1; i++) {
        assert nodes[i].next == nodes[i + 1];
    }
}

public static void main(String[] args) {
    Node[] nodes = new Node[100];
    for (int i = 0; i < nodes.length; i++) {
        nodes[i] = new Node();
    }
    for (int i = 0; i < nodes.length - 1; i++) {
        nodes[i].next = nodes[i + 1];
    }
    Node first = nodes[0];
    Node max = nodes[nodes.length - 1];

    max.next = null;
    assert !hasCycle(first);
    assertSameOrder(nodes);
    max.next = first;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = max;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = nodes[50];
    assert hasCycle(first);
    assertSameOrder(nodes);
}

Kura-kura dan kelinci

Lihatlah algoritma Pollard rho . Ini bukan masalah yang sama, tetapi mungkin Anda akan memahami logika darinya, dan menerapkannya untuk daftar tertaut.

(Jika Anda malas, Anda bisa memeriksa deteksi siklus - lihat bagian tentang kura-kura dan kelinci.)

Ini hanya membutuhkan waktu linier, dan 2 petunjuk tambahan.

Di Jawa:

boolean hasLoop( Node first ) {
    if ( first == null ) return false;

    Node turtle = first;
    Node hare = first;

    while ( hare.next != null && hare.next.next != null ) {
         turtle = turtle.next;
         hare = hare.next.next;

         if ( turtle == hare ) return true;
    }

    return false;
}

(Sebagian besar solusinya tidak memeriksa keduanya nextdan apakah ada next.nextnull. Juga, karena kura-kura selalu ada di belakang, Anda tidak perlu memeriksanya untuk null - kelinci sudah melakukannya.)

Pengguna unicornaddict memiliki algoritme yang bagus di atas, tetapi sayangnya itu berisi bug untuk daftar aneh yang panjangnya> = 3. Masalahnya adalah bahwa fastbisa "macet" tepat sebelum akhir daftar,slow menangkapnya, dan sebuah loop terdeteksi (salah).

Berikut algoritma yang diperbaiki.

static 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 = null;
        else
            fast = fast.next.next; // 2 hops.

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

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

Dalam konteks ini, ada banyak bahan teks di mana-mana. Saya hanya ingin memposting representasi diagram yang benar-benar membantu saya untuk memahami konsep tersebut.

Ketika cepat dan lambat bertemu pada titik p,

Jarak yang ditempuh dengan cepat = a + b + c + b = a + 2b + c

Jarak yang ditempuh lambat = a + b

Karena puasa 2 kali lebih cepat daripada lambat. Jadi a + 2b + c = 2 (a + b) , maka kita mendapatkan a = c .

Jadi ketika pointer lambat lainnya berjalan lagi dari kepala ke q , pada saat yang sama, pointer cepat akan berjalan dari p ke q , sehingga mereka bertemu di titik q bersama.

public ListNode detectCycle(ListNode head) {
    if(head == null || head.next==null)
        return null;

    ListNode slow = head;
    ListNode fast = head;

    while (fast!=null && fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;

        /*
        if the 2 pointers meet, then the 
        dist from the meeting pt to start of loop 
        equals
        dist from head to start of loop
        */
        if (fast == slow){ //loop found
            slow = head;
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }            
    }
    return null;
}

Algoritma

public static boolean hasCycle (LinkedList<Node> list)
{
    HashSet<Node> visited = new HashSet<Node>();

    for (Node n : list)
    {
        visited.add(n);

        if (visited.contains(n.next))
        {
            return true;
        }
    }

    return false;
}

Kompleksitas

Time ~ O(n)
Space ~ O(n)

Berikut ini mungkin bukan metode terbaik - itu adalah O (n ^ 2). Namun, itu harus berfungsi untuk menyelesaikan pekerjaan (pada akhirnya).

count_of_elements_so_far = 0;
for (each element in linked list)
{
    search for current element in first <count_of_elements_so_far>
    if found, then you have a loop
    else,count_of_elements_so_far++;
}

public boolean hasLoop(Node start){   
   TreeSet<Node> set = new TreeSet<Node>();
   Node lookingAt = start;

   while (lookingAt.peek() != null){
       lookingAt = lookingAt.next;

       if (set.contains(lookingAt){
           return false;
        } else {
        set.put(lookingAt);
        }

        return true;
}   
// Inside our Node class:        
public Node peek(){
   return this.next;
}

Maafkan saya ketidaktahuan saya (saya masih cukup baru untuk Java dan pemrograman), tetapi mengapa tidak bekerja di atas

Saya kira ini tidak menyelesaikan masalah ruang konstan ... tapi setidaknya sampai di sana dalam waktu yang masuk akal, benar? Ini hanya akan mengambil ruang dari daftar tertaut ditambah ruang dari himpunan dengan n elemen (di mana n adalah jumlah elemen dalam daftar tertaut, atau jumlah elemen hingga mencapai satu lingkaran). Dan untuk waktu, analisis kasus terburuk, saya pikir, akan menyarankan O (nlog (n)). Pencarian SortedSet untuk berisi () adalah log (n) (periksa javadoc, tapi saya cukup yakin struktur mendasar TreeSet adalah TreeMap, yang pada gilirannya adalah pohon merah-hitam), dan dalam kasus terburuk (tidak ada loop, atau loop di akhir), itu harus dilakukan n look-up.

Jika kita diizinkan untuk menanamkan kelas Node, saya akan memecahkan masalah karena saya sudah menerapkannya di bawah ini. hasLoop()berjalan dalam waktu O (n), dan hanya mengambil ruang dari counter. Apakah ini tampak seperti solusi yang tepat? Atau adakah cara untuk melakukannya tanpa menanamkan Node? (Jelas, dalam implementasi nyata akan ada lebih banyak metode, seperti RemoveNode(Node n), dll.)

public class LinkedNodeList {
    Node first;
    Int count;

    LinkedNodeList(){
        first = null;
        count = 0;
    }

    LinkedNodeList(Node n){
        if (n.next != null){
            throw new error("must start with single node!");
        } else {
            first = n;
            count = 1;
        }
    }

    public void addNode(Node n){
        Node lookingAt = first;

        while(lookingAt.next != null){
            lookingAt = lookingAt.next;
        }

        lookingAt.next = n;
        count++;
    }

    public boolean hasLoop(){

        int counter = 0;
        Node lookingAt = first;

        while(lookingAt.next != null){
            counter++;
            if (count < counter){
                return false;
            } else {
               lookingAt = lookingAt.next;
            }
        }

        return true;

    }



    private class Node{
        Node next;
        ....
    }

}

Anda bahkan dapat melakukannya dalam waktu O (1) yang konstan (walaupun itu tidak akan sangat cepat atau efisien): Ada jumlah node yang terbatas yang dapat disimpan oleh memori komputer Anda, kata N records. Jika Anda melintasi lebih dari N catatan, maka Anda memiliki lingkaran.

 // To detect whether a circular loop exists in a linked list
public boolean findCircularLoop() {
    Node slower, faster;
    slower = head;
    faster = head.next; // start faster one node ahead
    while (true) {

        // if the faster pointer encounters a NULL element
        if (faster == null || faster.next == null)
            return false;
        // if faster pointer ever equals slower or faster's next
        // pointer is ever equal to slower then it's a circular list
        else if (slower == faster || slower == faster.next)
            return true;
        else {
            // advance the pointers
            slower = slower.next;
            faster = faster.next.next;
        }
    }
}

boolean hasCycle(Node head) {

    boolean dec = false;
    Node first = head;
    Node sec = head;
    while(first != null && sec != null)
    {
        first = first.next;
        sec = sec.next.next;
        if(first == sec )
        {
            dec = true;
            break;
        }

    }
        return dec;
}

Gunakan fungsi di atas untuk mendeteksi loop dalam linkedlist di java.

Mendeteksi loop dalam daftar tertaut dapat dilakukan dengan salah satu cara paling sederhana, yang menghasilkan kompleksitas O (N) menggunakan hashmap atau O (NlogN) menggunakan pendekatan berbasis sort.

Saat Anda menelusuri daftar mulai dari kepala, buat daftar alamat yang diurutkan. Ketika Anda memasukkan alamat baru, periksa apakah alamat tersebut sudah ada di daftar yang disortir, yang membutuhkan kompleksitas O (logN).

Saya tidak dapat melihat cara apa pun untuk melakukan ini dengan jumlah waktu atau ruang yang tetap, keduanya akan bertambah dengan ukuran daftar.

Saya akan menggunakan IdentityHashMap (mengingat bahwa belum ada IdentityHashSet) dan menyimpan setiap Node ke dalam peta. Sebelum sebuah node disimpan, Anda akan memanggil containKey di atasnya. Jika Node sudah ada Anda memiliki siklus.

ItentityHashMap menggunakan == bukan .equals sehingga Anda memeriksa di mana objek berada di memori daripada jika memiliki konten yang sama.

Saya mungkin sangat terlambat dan baru untuk menangani utas ini. Tetapi tetap saja..

Mengapa alamat simpul dan simpul "selanjutnya" tidak dapat disimpan dalam sebuah tabel

Jika kita bisa melakukan tabulasi dengan cara ini

node present: (present node addr) (next node address)

node 1: addr1: 0x100 addr2: 0x200 ( no present node address till this point had 0x200)
node 2: addr2: 0x200 addr3: 0x300 ( no present node address till this point had 0x300)
node 3: addr3: 0x300 addr4: 0x400 ( no present node address till this point had 0x400)
node 4: addr4: 0x400 addr5: 0x500 ( no present node address till this point had 0x500)
node 5: addr5: 0x500 addr6: 0x600 ( no present node address till this point had 0x600)
node 6: addr6: 0x600 addr4: 0x400 ( ONE present node address till this point had 0x400)

Karenanya ada siklus yang terbentuk.

Ini kode runnable saya.

Apa yang saya lakukan adalah menghormati daftar yang ditautkan dengan menggunakan tiga node sementara (kompleksitas ruang O(1) ) yang melacak tautan.

Fakta menarik tentang melakukannya adalah untuk membantu mendeteksi siklus dalam daftar yang ditautkan karena ketika Anda maju, Anda tidak berharap untuk kembali ke titik awal (root node) dan salah satu node sementara harus pergi ke nol kecuali Anda memiliki siklus yang berarti menunjuk ke simpul root.

Kompleksitas waktu dari algoritma ini adalah O(n)dan kompleksitas ruang adalahO(1) .

Berikut adalah simpul kelas untuk daftar yang ditautkan:

public class LinkedNode{
    public LinkedNode next;
}

Berikut adalah kode utama dengan kasus uji sederhana dari tiga node yang menunjuk terakhir ke node kedua:

    public static boolean checkLoopInLinkedList(LinkedNode root){

        if (root == null || root.next == null) return false;

        LinkedNode current1 = root, current2 = root.next, current3 = root.next.next;
        root.next = null;
        current2.next = current1;

        while(current3 != null){
            if(current3 == root) return true;

            current1 = current2;
            current2 = current3;
            current3 = current3.next;

            current2.next = current1;
        }
        return false;
    }

Berikut ini adalah contoh kasus sederhana dari tiga node yang menunjuk ke node kedua:

public class questions{
    public static void main(String [] args){

        LinkedNode n1 = new LinkedNode();
        LinkedNode n2 = new LinkedNode();
        LinkedNode n3 = new LinkedNode();
        n1.next = n2;
        n2.next = n3;
        n3.next = n2;

        System.out.print(checkLoopInLinkedList(n1));
    }
}

Kode ini dioptimalkan dan akan menghasilkan hasil lebih cepat daripada dengan yang dipilih sebagai jawaban terbaik. Kode ini menyelamatkan dari proses yang sangat lama dalam mengejar pointer node maju dan mundur yang akan terjadi dalam kasus berikut jika kita mengikuti 'terbaik jawab metode. Lihatlah langkah-langkah berikut ini dan Anda akan menyadari apa yang saya coba katakan. Kemudian lihat masalahnya melalui metode yang diberikan di bawah ini dan ukur no. langkah-langkah yang diambil untuk menemukan jawabannya.

1-> 2-> 9-> 3 ^ -------- ^

Ini kodenya:

boolean loop(node *head)
{
 node *back=head;
 node *front=head;

 while(front && front->next)
 {
  front=front->next->next;
  if(back==front)
  return true;
  else
  back=back->next;
 }
return false
}

Ini solusi saya di java

boolean detectLoop(Node head){
    Node fastRunner = head;
    Node slowRunner = head;
    while(fastRunner != null && slowRunner !=null && fastRunner.next != null){
        fastRunner = fastRunner.next.next;
        slowRunner = slowRunner.next;
        if(fastRunner == slowRunner){
            return true;
        }
    }
    return false;
}

Anda dapat menggunakan algoritma kura-kura Floyd seperti yang disarankan dalam jawaban di atas juga.

Algoritma ini dapat memeriksa apakah daftar yang ditautkan sendiri memiliki siklus tertutup. Ini dapat dicapai dengan mengulang daftar dengan dua petunjuk yang akan bergerak dalam kecepatan yang berbeda. Dengan cara ini, jika ada siklus kedua pointer akan bertemu di beberapa titik di masa depan.

Silakan periksa posting blog pada struktur data daftar tertaut, di mana saya juga memasukkan potongan kode dengan implementasi algoritma yang disebutkan di atas dalam bahasa java.

Salam,

Andreas (@xnorcode)

Inilah solusi untuk mendeteksi siklus.

public boolean hasCycle(ListNode head) {
            ListNode slow =head;
            ListNode fast =head;

            while(fast!=null && fast.next!=null){
                slow = slow.next; // slow pointer only one hop
                fast = fast.next.next; // fast pointer two hops 

                if(slow == fast)    return true; // retrun true if fast meet slow pointer
            }

            return false; // return false if fast pointer stop at end 
        }

// fungsi loop daftar temukan tautan

int findLoop(struct Node* head)
{
    struct Node* slow = head, *fast = head;
    while(slow && fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            return 1;
    }
 return 0;
}

Pendekatan ini memiliki overhead ruang, tetapi implementasi yang lebih sederhana:

Loop dapat diidentifikasi dengan menyimpan node di Peta. Dan sebelum menempatkan node; periksa apakah node sudah ada. Jika node sudah ada di peta maka itu berarti Linked List memiliki loop.

public boolean loopDetector(Node<E> first) {  
       Node<E> t = first;  
       Map<Node<E>, Node<E>> map = new IdentityHashMap<Node<E>, Node<E>>();  
       while (t != null) {  
            if (map.containsKey(t)) {  
                 System.out.println(" duplicate Node is --" + t  
                           + " having value :" + t.data);  

                 return true;  
            } else {  
                 map.put(t, t);  
            }  
            t = t.next;  
       }  
       return false;  
  }  

public boolean isCircular() {

    if (head == null)
        return false;

    Node temp1 = head;
    Node temp2 = head;

    try {
        while (temp2.next != null) {

            temp2 = temp2.next.next.next;
            temp1 = temp1.next;

            if (temp1 == temp2 || temp1 == temp2.next) 
                return true;    

        }
    } catch (NullPointerException ex) {
        return false;

    }

    return false;

}