Struktur data - Bagaimanakah senarai pautan terbalik Java dilaksanakan?

Question

public class Node {
    public int value;
    public Node next;

    public Node(int data) {
        this.value = data;
    }


    public Node reverse(Node head) {
        Node pre = null;
        Node next = null;

        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;

        }
        return pre;


    }

Bagaimanakah kod ini terbalik dalam gelung while. Saya ingin menyahpenyahnya beberapa kali dan masih tidak dapat mengetahui perkara yang berlaku

Answer 1

Akan lebih mudah untuk memahami tujuan jika anda merujuknya. Bahagian yang paling mengelirukan adalah untuk menanganinya dari kanan ke kiri, kerana anda perlu menyimpan perkara di belakang dahulu, jika tidak, ia akan ditimpa dan hilang.

 pre        head       
+----+     +----+  +> +----+
|    |     |    |  |  |    |
|    |     |    |  |  |    |
|    |     |    |  |  |    |
+----+     +----+  |  +----+
|    |     |    |  |  |    |
|    |     |    |  |  |    |
+----+     +-+--+  |  +----+
             |     |
             +-----+

 pre        head       next        next = head.next;
+----+     +----+  +> +----+
|    |     |    |  |  |    |
|    |     |    |  |  |    |
|    |     |    |  |  |    |
+----+     +----+  |  +----+
|    |     |    |  |  |    |
|    |     |    |  |  |    |
+----+     +-+--+  |  +----+
             |     |
             +-----+

 pre        head       next
+----+ <+  +----+     +----+
|    |  |  |    |     |    |
|    |  |  |    |     |    |
|    |  |  |    |     |    |
+----+  |  +----+     +----+
|    |  |  |    |     |    |
|    |  |  |    |     |    |
+----+  |  +-+--+     +----+
        |    |                     head.next = pre;
        +----+
                       next
            pre        head        pre = head;
+----+ <+  +----+     +----+       head = next;
|    |  |  |    |     |    |
|    |  |  |    |     |    |
|    |  |  |    |     |    |
+----+  |  +----+     +----+
|    |  |  |    |     |    |
|    |  |  |    |     |    |
+----+  |  +-+--+     +----+
        |    |
        +----+

Answer 2

Ps: Adalah disyorkan untuk mengetahui lebih lanjut tentang senarai terpaut dahulu