Reverse a Doubly Linked List

Introduction

The linked list is one of the most important concepts to know while preparing for interviews. Having a good grasp of a linked list can be a huge plus point in coding interviews.

Problem Statement

In this problem, we will be given a doubly linked list as input, and we need to reverse it.

Problem Statement Understanding

According to the problem statement, we will be given a doubly-linked list, and we need to reverse the linked list.

Let's understand this problem with the help of some examples.

If the given doubly linked list is:

  • According to the problem statement we need to reverse this given list such that after reversing the list will look like:

Taking another example, if the given list is head -> 1 2 3 5 6 -> NULL.

  • In this case after reversing the list our list will look like: head -> 6 5 3 2 1 -> NULL.
Some more examples

Sample Input 1: 1 3 5 7 11 -> NULL.
Sample Output 1: 11 7 5 3 1 -> NULL.

Sample Input 2: 2 3 5 7 11 17 -> NULL.
Sample Output 2: 17 11 7 5 3 2 -> NULL.

Now, I think from the above examples, the problem statement is clear. Let’s see how we can approach it.

Before moving to the approach section, try to think about how you can approach this problem.

  • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach 1

This approach will be similar to reversing data present in an array.
1) We will initialize 2 pointers, one at starting and the other at the end of the linked list.
2) We will swap the node's data to which the pointers are pointing.
3) And then, we will move the pointers toward's each other by one step.
4) We will be performing step 2 and step 3 untill both the pointers do not cross each other or reach at the same position.
5) Finally, when both pointers reaches the same position, our doubly linked list will be fully reversed.

Time Complexity: O(n), 2 traversals will be required in this approach, one to get the address of the last node and another traversal to reverse the list.

Space Complexity: O(1)

The above approach will work fine, but the only issue is that we are traversing the linked list twice. Now we need to ask ourselves one simple question: Do we actually need two list traversals to reverse the linked list.

Is it possible to reverse the linked list in a single traversal?

  • Yes, it is possible, and we will see it in the following approach.

Let's move to next approach.

Approach 2

As we know that in a doubly linked list, we can access the previous as well as the next node of a given node, so it means that we can easily achieve reversal of the list by swapping the previous with next pointers of all nodes iteratively.

Let's move to the algorithm section to see the above approach in depth.

Algorithm

  • Create a pointer current. Initialize it with the head of the linked list.
  • Create a pointer temp. Initialize it with NULL.
  • Now swap current's prev and current's next using pointer temp.
  • Now move current to current's previous node because after swapping, current's prev stores the address of current's next node.
  • Repeat the process till current does not become NULL.

Dry run


Code Implementation:

#include 
using namespace std;

/* Node structure of a doubly linked list node */
class Node
{
    public:
    int data;
    Node* next;
    Node* prev;
};

/* Using this below function we will be adding a new node at beginning of the list */
void add_at_begin(Node** head, int x)
{
 
    Node* new_node = new Node();

    new_node->data = x;
 
    new_node->prev = NULL;
 
    new_node->next = (*head);
    
    if ((*head) != NULL)
        (*head)->prev = new_node;
 
    (*head) = new_node;
}

/* Using this below function we will be printing the content of the linked list */
void print_list(Node* node)
{
    while (node != NULL)
    {
        cout << node->data << ",";
        node = node->next;
    }
    cout<prev;
        current->prev = current->next;
        current->next = temp;            
        current = current->prev;
    }
     
    if(temp != NULL )
        *head = temp->prev;
}
 
/* Main function */
int main()
{
    Node* head = NULL;
 
    add_at_begin(&head, 17);
    add_at_begin(&head, 13);
    add_at_begin(&head, 1);
    add_at_begin(&head, 7);
    add_at_begin(&head, 2);
 
    cout<<"Initial linked list before reversing: "<

						 

Output

Initial linked list before reversing:
2,7,1,13,17,
Resultant reversed linked list:
17,13,1,7,2,

Time Complexity: O(n), where n is the number of nodes in the linked list

So, in this blog, we have tried to explain how you can reverse a doubly linked list in the most efficient way. This is a basic problem and is good for strengthening your concepts in LinkedList and if you want to practice more such problems, you can checkout Prepbytes (Linked List).

Previous post Sorted merge of two sorted doubly circular linked lists
Next post Length of longest palindrome list in a linked list using O(1) extra space

Leave a Reply

Your email address will not be published. Required fields are marked *