Why does this code fail to reverse a doubly linked list

Question

I tried avoiding to ask this question here, however after almost an hour looking at the same piece of code I really have no idea why the following code fails to reverse a doubly linked list:

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

I would appreciate any help.

EDIT It seems that the code has nothing to do with what I had in mind. Wow. As a side note, I have completed only the introductory programming course which doesn't cover pointers, let alone linked lists etc. Thank you for your help!

FINAL CODE If you are interested, I have finished my algorithm for reversing a doubly linked list. I think it is a nice approach, although I am open for suggestions of course.

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

I'd work somewhat differently. First reach the tail, then build a new list. And always prefetch the next element. I'll also say that changing the semantics of newTail during the code operating is code smell and may lead to confusion. And to mistakes. — Paul Stelian

robor robor · Accepted Answer · 2016-09-03T20:12:44

In the code the newTail is always one-behind iter. Inside the while-loop newTail->next is set to iter and iter->prev is set to newTail. Which has no effect.

Perhaps this diagram will help

Try this. It loops through the list and for each node swaps the next and prev pointers. (This might not be the most efficient algorithim.)

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

2 Answers