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

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

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

编辑 看来代码与我的想法无关。哇。附带说明一下，我只完成了入门编程类(class)，不包括指针，更不用说链表等了。感谢您的帮助!

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

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

在代码中，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;
}