wastefull.cpp

/*
   Reverse a doubly linked list, input list may also be empty
   Node is defined as
   struct Node
   {
     int data;
     Node *next;
     Node *prev;
   }
*/

Node* InsertNodeDLL(int data, Node* head)
{
    // initializing a new node
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    new_node->prev = NULL;
    
    // if empty list
    if(!head)
    {
        return new_node;
    }
    
    // traverser pointer
    Node* tail = head;
    
    // find the tail
    while(tail->next)
    {
        tail = tail->next;
    }
    
    // pointing to right places
    new_node->prev = tail;
    new_node->prev->next = new_node;
    
    //return the list
    return head;    
}

Node* Reverse(Node* head)
{
    if(!head)
    {
        return head;
    }
    
    Node* reverseddll;
    Node* trv_ptr = head;
    
    while(trv_ptr->next)
    {
        trv_ptr = trv_ptr->next;
    }
    
    while(trv_ptr)
    {
        reverseddll = InsertNodeDLL(trv_ptr->data, reverseddll);
        trv_ptr = trv_ptr->prev;
    }
    
    return reverseddll;
}