下面这个方法反转了一个包含 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
}
}
最佳答案
让我们尝试一次单步执行几行代码。
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;
}
关于java - 反转双向链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11166968/