扭转双向链接列表

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对于该情况为空):

所以我们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;
}