反转双向链表

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

- warpstar

---

为什么需要以这种方式反转DLL？只需使用尾指针从后面遍历即可。 - vijay

有关编程的内容：Does it matter?我知道这种解决方案可行，我只需要理解它是如何工作的...我需要将每次遍历发生的情况可视化。 - warpstar

每次你将指针向反方向移动并将p移动到下一个节点。你能清楚地告诉我你遇到了什么问题吗？ - Ajay Yadav

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

所以我们有 next 指向 A，prev 指向 B。 我们想要交换它们。 为此，我们将 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;
}

- cklab

---

此时，我们正在查看以下内容（注意：如果这是第一次迭代，则下一个指向null，但这并不重要，只需假设A在该情况下为null）：<--- 这就是我之前遇到的问题，但现在完全可以理解了。 - warpstar

啊，所以第一次迭代是导致你困扰的原因。如果你在图像中将字母“A”精神上替换为“null”，它应该会告诉你，它可以是“null”，因为你继续使用“B”。 - cklab

当你执行p=p.next时，它是如何转到下一个节点的？它不会向右遍历（就像在第一次迭代中它是null一样）...这意味着右侧没有节点。 - warpstar

p.next（或 A）以前是空的。如果您查看最终图像，您会发现当我们到达 p=p.next 时，p.next 指向 B，这可能是空的，也可能不是空的。 - cklab

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

}

请看这个图片。

希望你理解了。

谢谢

- vijay

---

这不会更新“prev”属性。请记住这是一个双向链表。 - Jorjon

Answer 3

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

Node currentNode=head;

while(currentNode!=null){
    Node temp = currentNode.next;
    currentNode.next=currentNode.prev;
    currentNode.prev=temp;
    currentNode=currentNode.prev;
}

- M Sach

Answer 4

使用头部双向链表，以下是我的理解。这有帮助吗？这正确吗？

当current在尾节点的前一个节点时，循环可能会被中断，但为了简单起见，让它到达尾部。 此外，在运行循环之前，通常会检查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. 
                    *

- RuntimeException

Answer 5

只需在列表的每个元素中交换prev和next指针即可。因此，您的评论是正确的。新头部的下一个指针确实从null开始。它被复制到其prev指针。作为列表的头部，它的prev当然应该是null。

Vj Shah的答案也是用不同的代码做同样的事情。

- sbkp

---

是的。我刚刚用图表清楚地表达了warpstar想要的内容。 - vijay

Answer 6

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

该算法基本上维护一个指向在反转后将成为列表第一个元素的条目的指针（refEntry）。

然后在迭代中删除列表的第一个元素，并在refEntry之后添加。

- hardik

Answer 7

这种反转的关键在于看一下简单的双向链表在反转前后的样子。一旦你看到需要反转列表的操作，这个方法就会更容易理解。

假设你有一个像这样的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
}

- dansalmo

Answer 8

我用Java编写的非递归版本 思路：先到达列表末尾，将该节点标记为新头部，然后开始向后方向移动，通过翻转连接/链接（next、prev）直到没有更多节点。

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

希望它有所帮助。

- i.AsifNoor