为什么此代码无法反转双向链表

Question

我试图避免在这里问这个问题，但是在查看同一段代码将近一个小时后，我真的不知道为什么以下代码无法反转双向链表：

Node* Reverse(Node* head) {
    if (head == nullptr) {return head;}
    Node *iter = head, *tail, *newTail;
    while (iter -> next != nullptr) {iter = iter -> next;} //to set the tail pointer
    tail = iter;
    newTail = tail; //the node that will become the tail after reversing is done
    iter = head;

    while (iter != tail) {
        newTail -> next = iter;
        iter -> prev = newTail;
        newTail = iter;
        iter = iter -> next;
    }

    newTail -> next = nullptr;
    tail -> prev = nullptr;
    return tail;
}

如有任何帮助，我将不胜感激。

EDIT 代码似乎与我的想法无关。哇。作为旁注，我只完成了入门编程课程，不包括指针，更不用说链表等了。谢谢你的帮助！

最终代码 如果您有兴趣，我已经完成了反转双向链表的算法。我认为这是一个很好的方法，尽管我当然愿意接受建议。

node *reverse(node *head)
{
    if (head == nullptr) {return head;}
    node *iter, *tail, *temp, *newTail;
    while (iter -> next != nullptr) {iter = iter -> next;}
    tail = iter;
    newTail = tail;
    iter = tail -> prev;
    while (iter != nullptr)
    {
        temp = iter -> prev;
        newTail -> next = iter;
        iter -> prev = newTail;
        newTail = iter;
        iter = temp;
    }
    tail -> prev = nullptr;
    newTail -> next = nullptr;
    return tail;
}

Answer 1

假设您有 3 个元素，将它们编号为 0、1、2。因此您从指向最后一个元素 (2) 的 newTail 开始。然后你从头开始（0），你设置newTail->next = iter。那么现在 2 链接到 0 了吗？这听起来不像是颠倒列表。

Answer 2

在代码中，newTail 总是落后于 iter。在 while 循环中，newTail->next 被设置为 iter，iter->prev 被设置为 newTail。哪个没有效果。

也许这张图会有帮助

试试这个。它遍历列表并为每个节点交换 next 和 prev 指针。（这可能不是最有效的算法。）

Node* Reverse2(Node* head) {
  if (head == nullptr) {return head;}
  Node *iter = head;

  Node *tail = nullptr;
  while (iter!=nullptr) {
    tail = iter; //keep track of tail

    Node *tmp = iter->next; //before swap, pre-fetch next node

    swap(iter);

    iter=tmp; //go to next node
  }

  return tail;

}

void swap(Node *n) {
  Node *tmp = n->prev;
  n->prev = n->next;
  n->next = tmp;
}

为什么此代码无法反转双向链表

Why does this code fail to reverse a doubly linked list

c++

linked-list

reverse

doubly-linked-list