扭转双向链接列表 [英] Reversing a Doubly Linked List

问题描述

这个方法正好在下面用n个元素反转双向链表。我不明白这是如何工作的。我添加了评论，如果我错了请纠正我。我不确定遍历过程是如何工作的。

This method right below reverses a doubly linked list with n elements. I dont understand how this really works. I have added comments, please correct me if I am wrong. I am not sure how the traversing process works.

 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
    }
 }

推荐答案

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

Let's try stepping through the code a few lines at a time.

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

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

Here we are just setting up some variables. We are swapping our head to point to the tail and the tail to the head.

现在我们定义我们的起始节点。这是我们的新头，曾经是尾巴。

Now we define our starting node. This is our new head that used to be the tail.

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

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

此时，这就是我们所看到的（注意：如果这是第一次迭代， next 将指向null，但这无关紧要，只假设A对于该情况为空）：

At this point, this is what we are looking at (note: if this is the first iteration, next would point to null but that doesn't matter, just assume A is null for that case):

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

So we have next pointing to A and prev pointing to B. We want these to be swapped. To do so, we go ahead and assign next to prev (which points to B) so now next and prev both point to B.

    p.next=p.prev; 

太棒了！我们到了一半。现在我们有：

Great! We're half way there. Now we have:

现在我们的最后一步是让 prev 指向 next 曾经指向。我们怎么去做呢？幸运的是，我们在 temp 中存储了用于指向（换句话说，A）的 next 。所以让我们用它来分配 prev 。

Now our last step is to have prev point to what next used to point to. How are we going to get to it? Luckily, we stored what next used to point to (in other words, A) in temp. So let's use that to assign prev.

    p.prev=temp; 

唉，我们有：

< img src =https://i.stack.imgur.com/kcPxV.pngalt =在此处输入图像说明>

现在这个节点已被交换，然后我们继续前进。

Now this node has been swapped, and we move on to the next.

    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;
}

这篇关于扭转双向链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！