反转双向链表

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 )：

​

所以我们有指向A的next和指向B的prev。为此，我们将next赋值给prev (它指向B)，所以现在next和prev都指向B。

    p.next=p.prev; 

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

​

​

现在，我们的最后一步是让prev指向next过去所指向的内容。我们怎么才能找到它呢？幸运的是，我们在temp中存储了next过去所指向的内容(换句话说，A)。所以让我们用它来赋值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;
}

Answer 2

希望这对你有帮助。

struct node* current = head;
struct node* next;
struct node* prev = NULL;



while (current != NULL)  //traverse the whole linked list 
{
   next  = current->next;  //temporarily store the next node
   current->next = prev;    //now assign the prev!node to next of current node
   prev = current;   //update the previous pointer
   current = next;  //update the current pointer

}

看看这张图。

​

希望你能得到它。

谢谢

Answer 3

它只是在列表的每个元素中交换前一个和下一个指针。所以你的评论是正确的。新的头的下一个指针从null开始。然后它被复制到它的prev指针。作为列表的头部，它的prev当然应该为null。

主播沙阿的答案是用不同的代码做同样的事情。