Part 26 of 26 in Linked List - set 02  

Reverse a doubly linked list by animeshn

Problem statement

Given a double linked list of integers as input, reverse the list.

Input

You need to write a function with signature "Node* Reverse(Node * head)", that will take address of the head node as argument. Your input list may also be empty.

Output

Your function must return address of the head node after reversal.

Here we implement reversing a Doubly linked list. When we reversed a singly linked list, we had to keep track of what the previous node was. (If you are not sure, read the editorial on reversing a singly linked list first.) Here, the same information is stored in node itself.

An important thing to notice here is that, in the final list, the previous element becomes the next element, and the next element becomes previous. So it is enough to swap the data members. We can either manually swap with a temporary variable.

Node *temp = current_node->prev;
current_node->prev = current_node->next;
current_node->next = temp;

But it is easy to make a mistake while manually implementing the swapping. We can avoid it by using the swap function available in the Standard Template Library (STL) for C++ users, available under the <algorithm> header file.

Now finally we need the last element's to be stored as the head. It is enough that we keep assigning the head variable until the end of the list. Finally head will contain the last element.

Time Complexity: O(n) to traverse the list once.

Space Complexity: O(1)

editorial written by ash1794

Node* Reverse(Node* head)
{
    Node* current_node = head; // Node Pointer to traverse the list.
    while(current_node != NULL)     //Traverse the list
    {
        swap(current_node->next,current_node->prev);    
        // Swap the next and previous pointers
        head = current_node;                            
        // Head is assigned the last node of the list

        // Note: The next node in the linked list is originally 
        // stored in current_node->next.But since we swapped them,
        // it is now storred in current_node->prev. 
        // To avoid confusion we can store current_node->next 
        // in a temporary variable, before swapping 
        // and then assign it to current_node.
        
        current_node = current_node->prev;  // Traverse Forward
    }
    
    return head;        //Return the new head of the linked list.
}

featured solution by ash1794



To try out your code



Sign in

Sign up