通过使用 'head.next' 而不是 'head' 作为起点来反转带有虚拟节点的双向链表

Question

首先，我有一个 reverse() 方法的有效实现，我不寻求有关如何实现它的帮助，因为这是一个家庭作业问题。我的问题是我运行执行了我认为会通过从列表中的第一个真实元素而不是 head 虚拟节点开始来节省 while 循环迭代的错误。

有效的reverse()方法代码：

public void reverse() {
  Node<T> current = head;
  Node<T> temp = null;

  tail = head; 

  while(current != null) {

    temp = current.prev;
    current.prev = current.next; 
    current.next = temp; 
    current = current.prev;
  }

  head = temp.prev;
}

并将其所属程序的示例运行放入错误中： https://ideone.com/KKUtMn

破坏我的程序的变化：

Node<T> current = head.next;

进行该更改会导致在调用 reverse() 之后对 addLast(x) 的任何调用都出现 NullPointerException。对 reverse() 的调用反转了列表，没有错误或问题，我可以调用 addFirst(x) 就好了，但是第一次调用 addLast(x) 会抛出异常。我发现它特别奇怪，因为对 addLast(x) 的调用使用 tail 虚拟节点来插入元素，但是 tail 在 reverse() 中的唯一用法是在循环并且不应受到任何 current 引用的影响。

我认为我会进行更改的原因是因为 head 的第一次迭代在 while 循环之后刚刚重新分配给 temp.prev 时似乎毫无用处。我也不需要循环提供的遍历，因为我可以从一开始就直接指向第一个非虚拟节点。我显然是错的，因为这个想法行不通，但我无法弄清楚造成这种情况的逻辑。

有什么想法吗？

Answer 1

问题是你一开始还是设置了tail = head。由于您永远不会颠倒前一个头部的上一个和下一个，因此它不会有上一个，只有下一个。当您调用 addLast 时会导致 NullPointerException 并且他试图获取尾部的 prev ;)

Answer 2

您可以移至列表末尾

while(current.next != null){
    current = current.next;

如果你在最后，你开始交换节点的下一个引用...

current.next = curr.prev

等等

通过使用 'head.next' 而不是 'head' 作为起点来反转带有虚拟节点的双向链表

Reversing a doubly-linked list with dummy nodes by using 'head.next' as a start point instead of 'head'

java

while-loop

doubly-linked-list