CODEWITHSUNDEEP
c++linked-listreversedoubly-linked-list
Oran Can Ören
Oran Can Ören

Reputation: 117

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

Upvotes: 0

Views: 105

Answers (2)

robor
robor

Reputation: 3089

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

Upvotes: 1

grigor
grigor

Reputation: 1624

Let say you have 3 elements, number them 0, 1, 2. So you start off with newTail pointing to the last element (2). Then you start from the beginning (0) and you set newTail->next = iter. So now 2 is linked to 0? That doesn't sound like reversing the list.

Upvotes: 0

Related Questions