Data structure - How is Java flipped linked list implemented?
習慣沉默
習慣沉默 2017-06-23 09:13:13
0
2
886
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;


    }

How does this code flip in the while loop? I want to be more detailed. I debugged it several times and still don’t understand what’s going on.

習慣沉默
習慣沉默

reply all(2)
大家讲道理

It will be easier to understand the purpose if you refer to it. The most confusing part is to deal with it from right to left, because you have to save the things at the back first, otherwise they will be overwritten and lost.

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

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

 pre        head       next
+----+ <+  +----+     +----+
|    |  |  |    |     |    |
|    |  |  |    |     |    |
|    |  |  |    |     |    |
+----+  |  +----+     +----+
|    |  |  |    |     |    |
|    |  |  |    |     |    |
+----+  |  +-+--+     +----+
        |    |                     head.next = pre;
        +----+
                       next
            pre        head        pre = head;
+----+ <+  +----+     +----+       head = next;
|    |  |  |    |     |    |
|    |  |  |    |     |    |
|    |  |  |    |     |    |
+----+  |  +----+     +----+
|    |  |  |    |     |    |
|    |  |  |    |     |    |
+----+  |  +-+--+     +----+
        |    |
        +----+
过去多啦不再A梦

Ps: It is recommended to learn more about linked lists first

Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template