反转双向链表 [英] 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 为 null案件):

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 中存储了 next 用来指向的内容(换句话说，A).所以让我们用它来分配 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; 

唉，我们有:

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

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屋！