时间戳

首页 > 解决方案 > 双向链表问题。一次迭代会是什么样子？

java - 双向链表问题。一次迭代会是什么样子？

问题描述

class Node {

public Node prev;
public int item;
public Node next;

public Node(Node p, int i, Node n) {
    prev = p;
    item = i;
    next = n;
}

}

这是节点类。

这是我必须看透的。

p = list; 
while ( p != null) {     
   q = p.next;     
   p.next = p.prev;     
   p.prev = q;     
   list = p;     
   p = q; 
};

我的节点列表最初是这样的：null -> 1 -> 2 -> 3 -> 4 -> 5 -> null

这就是我第一次经历 while 循环的过程，我只是想确保它是正确的。

列表 = 空 2 3 4 5 1 空

p = 空 2 3 4 5 空

q = 空 2 3 4 5 空

我对格式表示歉意，我是在堆栈溢出中发帖的新手。

标签： javadoubly-linked-list

解决方案

您的代码实际上是在还原双向链表。

特别是在第一次迭代之后，您有以下状态：

p: null -> 2 -> 3 -> 4 -> 5 -> null
q: null -> 2 -> 3 -> 4 -> 5 -> null
list: null -> 1 -> null

以下是如何逐次查看方法迭代的状态：

class Answer {
  static class Node {
    int item;
    Node prev;
    Node next;

    Node(int item) {
      this.item = item;
      this.prev = null;
      this.next = null;
    }

    static Node of(int item) {
      return new Node(item);
    }

    Node link(Node next) { 
      this.next = next;
      next.prev = this;
      return next;
    }

    @Override
    public String toString() {
      String res = "null -> " + this.item + " -> ";
      Node node = this;
      while (node != null) {
        res += (node.next == null) ? "null" : (node.next.item + " -> ");
        node = node.next;
      }
      return res;
    }
  }

   public static void main(String[] args) {
    // initialize: null -> 1 -> 2 -> 3 -> 4 -> 5 -> null
    Node root = Node.of(1);
    root.link(Node.of(2))
        .link(Node.of(3))
        .link(Node.of(4))
        .link(Node.of(5));
    reverse(root);
  }

  static void reverse(Node list) {
    int iteration = 1;
    Node p = list; 
    Node q = null;
    while ( p != null) {
       q = p.next;     
       p.next = p.prev;     
       p.prev = q;     
       list = p;     
       p = q; 
       printIteration(iteration++, p, q, list);
    }
  }

  static void printIteration(int iteration, Node p, Node q, Node list) {
    System.out.println();
    System.out.println("iteration " + iteration);
    System.out.println("p: " + p);
    System.out.println("q: " + q);
    System.out.println("list: " + list);
  }
}

推荐阅读