Oran Can Oren - 1 year ago 66

C++ 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.

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 Source

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