6

下面的这个方法反转了一个包含 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
    }
 }
4

8 回答 8

26

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

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;

伟大的！我们已经成功了一半。现在我们有：

第2步

现在我们的最后一步是指向过去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;
}
于 2012-06-23T05:33:28.910 回答
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

}

看这个图。 在此处输入图像描述

希望你能明白。

谢谢

于 2012-06-23T05:01:01.837 回答
1

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

Vj shah 的回答只是用不同的代码做同样的事情。

于 2012-06-23T05:11:57.130 回答
1

使用标题双向链接列表，以下是我的理解。这有帮助吗？它是否正确？

当 current 在 tail 后面一个节点时，循环可能会被打破，但为简单起见，让它到达 tail。此外，通常在运行循环之前检查 0 或 1 大小的列表。

H   1   2   3   4   5   //current pointer at head
*

H   5   1   2   3   4   //bring current tail to the next of current pointer. Update current tail.
*

H   5   1   2   3   4   //advance current pointer to next
    *

H   5   4   1   2   3   //bring current tail to the next of current pointer. Update current tail.
    *

H   5   4   1   2   3   //advance current pointer to next
        *

H   5   4   3   1   2   // and so on.. 
        *

H   5   4   3   1   2
            *

H   5   4   3   2   1
            *

H   5   4   3   2   1
                *

H   5   4   3   2   1
                *

H   5   4   3   2   1   //break out when current pointer is at the tail. 
                    *
于 2016-05-08T07:11:24.693 回答
1

为了简单起见，它也可以从头节点开始，否则算法保持不变：

Node currentNode=head;

while(currentNode!=null){
    Node temp = currentNode.next;
    currentNode.next=currentNode.prev;
    currentNode.prev=temp;
    currentNode=currentNode.prev;
}
于 2016-07-06T14:10:16.273 回答
0

这种反转如何工作的关键是查看一个简单的双向链表在反转之前和之后的样子。一旦你看到反转列表需要做什么，这个方法就会更容易理解。

假设你有一个Nodes这样的第一个节点在 0：

node       0    1    2    3    4
data       A    L    I    S    T
next       1    2    3    4   null
prev      null  0    1    2    3

从 0 开始遍历上面的节点给出输出： ALIST

保留每个节点的数据，您可以通过交换每个节点的 prev 和 next 节点值来反转列表：

node       0    1    2    3    4
data       A    L    I    S    T
next      null  0    1    2    3
prev       1    2    3    4   null

从 4 开始遍历上面的节点给出输出：TSILA

假设您有这样的 Node 类，执行此操作的代码很简单：

public class Node {
    private char ch;
    private Node next;
    private Node prev;
}

public static Node reverse(Node trav) {
    Node swapped;
        while (trav != null) {
            swapped.next = trav.prev;
            swapped.prev = trav.next;
            trav = swap;
            trav = trav.prev;  // it was swapped so you need to follow prev
            }
        return trav  // return the new head node
}
于 2013-10-29T23:06:35.173 回答
0 
public void reverseList(){

    Entry<E> refEntry = header.previous;
    for(int i = 0; i < size-1; i++){
        Entry<E> first = header.next;
        first.next.previous = first.previous;
        first.previous.next = first.next;

        first.previous = refEntry;
        first.next = refEntry.next;
        refEntry.next.previous = first;
        refEntry.next = first;
    }
    refEntry.previous = header;
}

该算法基本上维护一个pointer(refEntry)条目，该条目将在反转后成为列表中的第一个元素。

然后在迭代中删除列表的第一个元素并在refEntry.

于 2014-02-02T07:42:05.470 回答
0

我在 Java Idea 后面写的没有递归的版本：首先到达列表的末尾，将此节点标记为新的头，然后通过翻转连接/链接（下一个，上一个）开始向后移动，直到你没有更多的节点。

 Node Reverse(Node head) {
        //If List is empty or having one node
        if (head == null || head.next == null) return head;

        //Else
        Node current = head;

        //First move to the end of list
        while (current.next != null) {
            current = current.next;
        }
        //Shift head at tail of list
        head = current;

        //Let the magic begin
        while (current != null) {
                Node prev = current.prev;
                current.prev = current.next;
                current.next = prev;
                current = prev;
        }


        return head;
    }

我希望它有所帮助。

于 2017-10-17T09:10:33.897 回答