CODEWITHSUNDEEP
c++algorithm
erol yeniaras
erol yeniaras

Reputation: 3797

Simpler approach to "reversing a doubly linked list" does not work for some reason

I am aware that "Reversing a doubly linked list" has been asked and answered before, e.g.: Reversing a Doubly Linked List But my question a little different.

All the methods that I could find online use a "current node (curr)" iterator and do the swapping on that as follows:

Node* Reverse(Node* head)
{
    Node* curr=head;
    while(curr)
    {
        swap(curr->next, curr->prev);
        head=curr;

        curr=curr->prev;
    }
    return head;
}

where the node is of type:

struct Node
{
  int data;
  Node *next;
  Node *prev
}

Now the question is, I tried to simplify that code by omitting the curr iterator since it looks totally unnecessary to me. Here is the new code:

Node* Reverse(Node* head)
{
    while(head)
    {
        swap(head->next, head->prev);

        if(head->prev) head=head->prev;
    }
    return head;
}

This works on paper however When I test it in an online compiler I get time limit exceeded error: http://www.mycodeschool.com/problems/reverse-a-doubly-linked-list

I believe that we can make all the swapping on the head node and then iterate it to the prev node.

Do you see any logical problems with this code?

Upvotes: 1

Views: 141

Answers (1)

Lingxi
Lingxi

Reputation: 14967

Node* Reverse(Node* head)
{
    while(head)
    {
        swap(head->next, head->prev);

        if(head->prev) head=head->prev;
        else break;  // !!!
    }
    return head;
}

Upvotes: 2

Related Questions