Oran Can Oren Oran Can Oren - 2 months ago 10
C++ Question

Why does this code fail to reverse a doubly linked list

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 ofcourse.

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

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

enter image description here

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