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) {
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

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)
{
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;
}
``````

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) {

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