java - 反转双向链表

Question

下面这个方法反转了一个包含 n 个元素的双向链表。我不明白这是怎么回事。我已经添加了评论，如果我错了请纠正我。我不确定遍历过程是如何工作的。

 public void reverseDLL( ) {
   Node temp=head; //swap head and tail
   head=tail; // head now points to tail
   tail=temp; //tail points to head
    //traverse the list swapping prev and next fields of each node
  Node p=head; //create a node and point to head

  while(p!=null) //while p does not equal null
    { //swap prev and next of current node
      temp=p.next; // p.next does that not equal null? confusing.
      p.next=p.prev; //this line makes sense since you have to reverse the link
      p.prev=temp; //having trouble visualizing this.
      p=p.next;//advance current node which makes sense
    }
 }

Answer 1

让我们尝试一次单步执行几行代码。

Node temp=head;
head=tail;
tail=temp;

这里我们只是设置了一些变量。我们交换头指向尾部，尾部指向头。

现在我们定义起始节点。这是我们的新头，以前是尾部。

Node p=head; //create a node and point to head

while(p!=null)
{ 
    temp=p.next; 

此时，这就是我们正在查看的内容(注意:如果这是第一次迭代，next 将指向 null 但这并不重要，只需假设 A 为 null案件):

所以我们有 next 指向 A 和 prev 指向 B。我们希望交换它们。为此，我们继续将 next 分配给 prev(指向 B)，所以现在 next 和 prev 都指向 B。

    p.next=p.prev; 

太棒了!我们已经完成了一半。现在我们有:

现在我们的最后一步是让 prev 指向 next 过去指向的地方。我们将如何做到这一点？幸运的是，我们将 next 用来指向(换句话说，A)的内容存储在 temp 中。所以让我们用它来分配 prev。

    p.prev=temp; 

唉，我们有:

现在这个节点已经交换了，我们继续下一个。

    p=p.next;
}

冲洗并重复。

一起:

Node p=head; //create a node and point to head

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