Reverse a Doubly Linked List

Problem Statement: Given a doubly linked list of size ‘N’ consisting of positive integers, your task is to reverse it and return the head of the modified doubly linked list.

Examples

Example 1:

Input Format:

DLL: 1 <-> 2 <-> 3 <-> 4

Result: DLL: 4 <-> 3 <-> 2 <-> 1

Explanation: The doubly linked list is reversed and its last node is returned at the new head pointer.

Example 2:

Input Format:

DLL: 10 <-> 20 <-> 30

Result: DLL: 30 <-> 20 <-> 10

Explanation: In this case, the doubly linked list is reversed and its former tail is returned as its new head.

Practice:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Brute Force Approach Optimal Approach

Expand any one approach by clicking the given options in the bar. Clicking one approach on bar, closes all other expands. You can manually expand more than one approach at a time

Brute Force Approach
Algorithm / Intuition

A brute-force approach involves replacing data in a doubly linked list. First, we traverse the list and store node data in a stack. Then, in a second pass, we assign elements from the stack to nodes, ensuring a reverse order replacement since stacks follow the Last-In-First-Out (LIFO) principle.

Algorithm:

Step 1: Initialization a temp pointer to the head of the doubly linked list and a stack data structure to store the values from the list.

Step 2: Traverse the doubly linked list with the temp pointer and while traversing push the value at the current node temp onto the stack. Move the temp to the next node continuing until temp reaches null indicating the end of the list.

Step 3: Reset the temp pointer back to the head of the list and in thissecond iteration pop the element from the stack, replace the data at the current node with the popped value from the top of the stack and move temp to the next node. Repeat this step until temp reaches null or the stack becomes empty.

Code

#include <bits/stdc++.h>

using namespace std;

// Define a Node class for doubly linked list
class Node {
public:
    // Data stored in the node
    int data;   
    // Pointer to the next node in the list 
    //(forward direction)
    Node* next;     
    // Pointer to the previous node in the list
    //(backward direction)
    Node* back;     

    // Constructor for a Node with both data,
    //a reference to the next node,
    //and a reference to the previous node
    Node(int data1, Node* next1, Node* back1) {
        data = data1;
        next = next1;
        back = back1;
    }

    // Constructor for a Node with data,
    //and no references to the next and
    //previous nodes (end of the list)
    Node(int data1) {
        data = data1;
        next = nullptr;
        back = nullptr;
    }
};

// Function to convert an array
// to a doubly linked list
Node* convertArr2DLL(vector<int> arr) {
    // Create the head node with
    //the first element of the array
    
    Node* head = new Node(arr[0]);
    
    // Initialize 'prev' to the head node
    Node* prev = head;            

    for (int i = 1; i < arr.size(); i++) {
        // Create a new node with data from the
        //array and set its 'back' pointer to
        //the previous node
        
        Node* temp = new Node(arr[i], nullptr, prev);
        // Update the 'next' pointer of the
        //previous node to point to
        //the new node
        prev->next = temp; 
         // Move 'prev' to the newly created
         //node for the next iteration
        prev = temp;       
    }
    // Return the head of the doubly linked list
    return head;  
}

// Function to print the elements
//of the doubly linked list
void print(Node* head) {
    while (head != nullptr) {
        // Print the data in the tail node
        cout << head->data << " ";  
         // Move to the next node
        head = head->next;         
    }
}

 
// Funcion to reverse a doubly linked list
// Stack Brute Force Approach
Node* reverseDLL(Node* head){
    // if head is empty or there is only one element
    // we can directly just return the head
    if(head==NULL || head->next == NULL){
        return head;
    }
    
    // Initialise a stack st
    stack<int> st;
    
    // Initialise the node pointer temp at head
    Node* temp = head;
    
    // Traverse the doubly linked list via the temp pointer
    while(temp!=NULL){
        // insert the data of the current node into the stack
        st.push(temp->data);
        // traverse further
        temp = temp->next;
    }
    
    // Reinitialise temp to head
    temp = head;
    
    // Second iteration of the DLL to replace the values
    while(temp!=NULL){
        // Replace the value pointed via temp with
        // the value from the top of the stack
        temp->data = st.top();
        // Pop the value from the stack
        st.pop();
        // Traverse further
        temp = temp->next;
    }
    
    // Return the updated doubly linked 
    // where the values of nodes from both ends 
    // has been swapped
    return head;

}


int main() {
    vector<int> arr = {12, 5, 8, 7, 4};
    Node* head = convertArr2DLL(arr);
    cout << endl << "Doubly Linked List Initially:  " << endl;
    print(head);
    cout << endl << "Doubly Linked List After Reversing " << endl;
    
     // Insert a node with value 10 at the end
    head = reverseDLL(head);
    print(head);
}



import java.util.Stack;

public class DLinkedList {
    public static class Node {
        // Data stored in the node
        public int data;
        // Reference to the next node
        //in the list (forward direction)
        public Node next;
        // Reference to the previous nod
        //in the list (backward direction)
        public Node back;

        // Constructor for a Node with both data, 
        //a reference to the next node, and a
        //reference to the previous node
        public Node(int data1, Node next1, Node back1) {
            data = data1;
            next = next1;
            back = back1;
        }

        // Constructor for a Node with data,
        //and no references to the next and
        //previous nodes (end of the list)
        public Node(int data1) {
            data = data1;
            next = null;
            back = null;
        }
    }

    private static Node convertArr2DLL(int[] arr) {
        // Create the head node with the
        //first element of the array
        Node head = new Node(arr[0]);
        // Initialize 'prev' to the head node
        Node prev = head;

        for (int i = 1; i < arr.length; i++) {
            // Create a new node with data from
            // the array and set its 'back' pointer
            // to the previous node
            
            Node temp = new Node(arr[i], null, prev);
            // Update the 'next' pointer of the
            // previous node to point to the new node
            
            prev.next = temp;
            // Move 'prev' to the newly created node
            //for the next iteration
            prev = temp;
        }
        // Return the head of the doubly linked list
        return head;
    }

    private static void print(Node head) {
        while (head != null) {
            // Print the data in the current node
            System.out.print(head.data + " ");
            // Move to the next node
            head = head.next; 
        }
        System.out.println();
    }
    
        // Initialise a stack st
    Stack<Integer> st = new Stack<>();
    
    // Initialise the node pointer temp at head
    Node temp = head;
    
    // Traverse the doubly linked list via the temp pointer
    while(temp!=null){
        // insert the data of the current node into the stack
        st.push(temp.data);
        // traverse further
        temp = temp.next;
    }
    
    // Reinitialise temp to head
    temp = head;
    
    // Second iteration of the DLL to replace the values
    while(temp!=null){
        // Replace the value pointed via temp with
        // the value from the top of the stack and pop it
        temp.data = st.pop();

        // Traverse further
        temp = temp.next;
    }
    
    // Return the updated doubly linked 
    // where the values of nodes from both ends 
    // has been swapped
    return head;

    }

    

    public static void main(String[] args) {
        int[] arr = {12, 5, 6, 8, 4};
        // Convert the array to a doubly linked list
        Node head = convertArr2DLL(arr);

        // Print the doubly linked list
        System.out.println(“Doubly Linked List Initially:  “);
        print(head);

        System.out.println("Doubly Linked List After Reversing :");

        head = reverseDLL(head);
        print(head);

    }
}


class Node:
    def __init__(self, data, next_node=None, back_node=None):
        # Data stored in the node
        self.data = data
        # Reference to the next node
        # in the list (forward direction)
        self.next = next_node
        # Reference to the previous node
        # in the list (backward direction)
        self.back = back_node

def convert_arr_to_dll(arr):
    # Create the head node with
    # the first element of the array
    head = Node(arr[0])
    # Initialize 'prev' to the head node
    prev = head

    for i in range(1, len(arr)):
        # Create a new node with data from the
        # array and set its 'back' pointer
        # to the previous node
        temp = Node(arr[i], None, prev)
        
        # Update the 'next' pointer of the
        # previous node to point to the new node
        prev.next = temp
        # Move 'prev' to the newly created 
        # node for the next iteration
        prev = temp

    # Return the head of the doubly linked list
    return head

def print_dll(head):
    while head is not None:
        # Print the data in the current node
        print(head.data, end=" ")
        # Move to the next node
        head = head.next
    print()


def reverse_dll(head):
    # If head is empty or there is only
    # one element, return the head directly
    if head is None or head.next is None:
        return head

    # Initialize a stack to store values
    st = []
    # Initialize the node pointer
    #'temp' at head
    temp = head

    # Traverse the doubly linked list
    # via the 'temp' pointer
    while temp is not None:
        # Insert the data of the current
        # node into the stack
        st.append(temp.data)
        # Traverse further
        temp = temp.next

    # Reinitialize 'temp' to head
    temp = head

    # Second iteration of the DLL
    # to replace the values
    while temp is not None:
        # Replace the value pointed to
        # by 'temp' with the value from
        # the top of the stack and pop it
        temp.data = st.pop()
        # Traverse further
        temp = temp.next

    # Return the updated doubly linked list
    # where the values of nodes from both
    # ends have been swapped
    return head


# Example usage:
arr = [12, 5, 6, 8, 4]
# Convert the array to a
# doubly linked list
head = convert_arr_to_dll(arr)
# Print the doubly linked list
print('Doubly Linked List Initially:  ')
print_dll(head)

print('Doubly Linked List After Reversing :')

# Reverse the doubly linked list
head = reverse_dll(head)
# Print the reversed doubly linked list
print_dll(head)



// Define the Node class for a doubly linked list
class Node {
    constructor(data, next, back) {
        this.data = data;
        this.next = next;
        this.back = back;
    }
}

// Function to convert an array
// to a doubly linked list
function convertArr2DLL(arr) {
    // Create the head node with 
    // the first element of the array
    let head = new Node(arr[0]);
    // Initialize 'prev' to the head node
    let prev = head;

    for (let i = 1; i < arr.length; i++) {
        // Create a new node with data from
        // the array and set its 'back' pointer
        // to the previous node
        let temp = new Node(arr[i], null, prev);
        // Update the 'next' pointer of the
        // previous node to point to the new node
        prev.next = temp;
        // Move 'prev' to the newly created
        // node for the next iteration
        prev = temp;
    }
    // Return the head of the
    // doubly linked list
    return head;
}

// Function to print the elements
// of the doubly linked list
function print(head) {
    while (head !== null) {
        // Print the data in the current node
        console.log(head.data + " ");
        // Move to the next node
        head = head.next;
    }
    console.log();
}

// Function to reverse the data of a doubly linked list
function reverseDLL(head) {
    if (head === null || head.next === null) {
        // If the list is empty or has only one element, no need to reverse
        return head;
    }

    let st = []; // Create a stack to store data temporarily
    let temp = head;

    // First iteration: Push data into the stack while traversing
    while (temp !== null) {
        st.push(temp.data);
        temp = temp.next;
    }

    temp = head;

    // Second iteration: Pop data from the stack and update the list's nodes
    while (temp !== null) {
        temp.data = st.pop();
        temp = temp.next;
    }

    return head;
}

const arr = [12, 5, 6, 8, 4];
// Convert the array to a doubly linked list
let head = convertArr2DLL(arr);
// Print the doubly linked list
console.log("Doubly Linked List Initially:  ");
print(head);

console.log("Doubly Linked List After Reversing :");

head = reverseDLL(head);
print(head);


Output: Doubly Linked List Initially: 12 5 6 8 4 Doubly Linked List After Reversing : 4 8 6 5 12

Complexity Analysis

Time Complexity : O(2N) During the first traversal, each node’s value is pushed into the stack once, which requires O(N) time. Then, during the second iteration, the values are popped from the stack and used to update the nodes. Space Complexity : O(N) This is because we are using an external stack data structure. At the end of the first iteration, the stack will hold all N values of the doubly linked list therefore the space required for stack is directly proportional to the size of the input doubly linked list.

Optimal Approach
Algorithm / Intuition

Reverse the Links in a Single Traversal

Instead of performing two separate traversals of the linked list and storing its node values in an external data structure, we can optimize our approach by directly modifying the links between the nodes within the doubly linked list in place, as visualized below:

We need to traverse on every node, and for every node change the next pointer and back pointer. If we can do this for all nodes, at the end of traversal, the doubly linked list will be reversed.

Algorithm:

Step 1: Initialise two pointers that are needed for the reversal. Initialize a current pointer to the head of the linked list. This pointer will traverse the list as we reverse it. Initialize a second pointer last to null. This pointer will be used for temporary storage during pointer swapping, as we need a third variable while swapping two data.

Step 2: Traverse through the DLL by looping over all the nodes..

Step 3: While iterating over all nodes in the linked list, we make changes to set the backward pointer of a node to the next changing its previous link. Along with this, the forward pointer is adjusted to point to the previous node, reversing the next link. To prevent losing the last node in this process, we use a reference to the last node to retain it.

  • Update the current node’s back pointer to point to the next node (current->back = current->next). This step reverses the direction of the backward pointer.
  • Update the current node’s next pointer to point to the previous node (current->next = last). This step reverses the direction of the forward pointer.
  • Move the current pointer one step forward (current = current->back). This allows us to continue the reversal process.

Step 4: After completing the traversal, the last node ends up at the second node in the reversed doubly linked list. To obtain the new head of the reversed list, we simply use the backward pointer of the last node, which points to the new head.

To ensure that we handle the case where the traversal ended at the original list’s end (i.e., the last pointer is not null), we update the head pointer to point to the new head of the reversed list, which is stored in the last pointer.

Finally, we return the head pointer, now pointing to the head of the fully reversed doubly linked list.

Code

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Define a Node class for doubly linked list
class Node {
public:
    // Data stored in the node
    int data;   
    // Pointer to the next node in the list 
    //(forward direction)
    Node* next;     
    // Pointer to the previous node in the list
    //(backward direction)
    Node* back;     

    // Constructor for a Node with both data,
    //a reference to the next node,
    //and a reference to the previous node
    Node(int data1, Node* next1, Node* back1) {
        data = data1;
        next = next1;
        back = back1;
    }

    // Constructor for a Node with data,
    //and no references to the next and
    //backious nodes (end of the list)
    Node(int data1) {
        data = data1;
        next = nullptr;
        back = nullptr;
    }
};

// Function to convert an array
// to a doubly linked list
Node* convertArr2DLL(vector<int> arr) {
    // Create the head node with
    //the first element of the array
    
    Node* head = new Node(arr[0]);
    
    // Initialize 'prev' to the head node
    Node* prev = head;            

    for (int i = 1; i < arr.size(); i++) {
        // Create a new node with data from the
        //array and set its 'back' pointer to
        //the previous node
        
        Node* temp = new Node(arr[i], nullptr, prev);
        // Update the 'next' pointer of the
        //previous node to point to
        //the new node
        prev->next = temp; 
         // Move 'prev' to the newly created
         //node for the next iteration
        prev = temp;       
    }
    // Return the head of the doubly linked list
    return head;  
}

// Function to print the elements
//of the doubly linked list
void print(Node* head) {
    while (head != nullptr) {
        // Print the data in the tail node
        cout << head->data << " ";  
         // Move to the next node
        head = head->next;         
    }
}

 
// Function to reverse a doubly linked list
// In-place link exchange method
Node* reverseDLL(Node* head) {
    
    // Check if the list is empty
    // or has only one node
    if (head == NULL || head->next == NULL) {
        // No change is needed;
        // return the current head
        return head; 
    }
    
     // Initialize a pointer to
     // the previous node
    Node* prev = NULL;  
    
    // Initialize a pointer to
    // the current node
    Node* current = head;   

    // Traverse the linked list
    while (current != NULL) {
        // Store a reference to
        // the previous node
        prev = current->back; 
        
        // Swap the previous and
        // next pointers
        current->back = current->next; 
        
        // This step reverses the links
        current->next = prev;          
        
        // Move to the next node
        // in the original list
        current = current->back; 
    }
    
    // The final node in the original list
    // becomes the new head after reversal
    return prev->back;
}


int main() {
    vector<int> arr = {12, 5, 8, 7, 4};
    Node* head = convertArr2DLL(arr);
    cout << endl << "Doubly Linked List Initially:  " << endl;
    print(head);
    cout << endl << "Doubly Linked List After Reversing " << endl;
    
     // Insert a node with value 10 at the end
    head = reverseDLL(head);
    print(head);

    return 0;
}


import java.util.Stack;

public class DLinkedList {
    public static class Node {
        // Data stored in the node
        public int data;
        // Reference to the next node
        //in the list (forward direction)
        public Node next;
        // Reference to the previous nod
        //in the list (backward direction)
        public Node back;

        // Constructor for a Node with both data, 
        //a reference to the next node, and a
        //reference to the previous node
        public Node(int data1, Node next1, Node back1) {
            data = data1;
            next = next1;
            back = back1;
        }

        // Constructor for a Node with data,
        //and no references to the next and
        //previous nodes (end of the list)
        public Node(int data1) {
            data = data1;
            next = null;
            back = null;
        }
    }

    private static Node convertArr2DLL(int[] arr) {
        // Create the head node with the
        //first element of the array
        Node head = new Node(arr[0]);
        // Initialize 'prev' to the head node
        Node prev = head;

        for (int i = 1; i < arr.length; i++) {
            // Create a new node with data from
            // the array and set its 'back' pointer
            // to the previous node
            
            Node temp = new Node(arr[i], null, prev);
            // Update the 'next' pointer of the
            // previous node to point to the new node
            
            prev.next = temp;
            // Move 'prev' to the newly created node
            //for the next iteration
            prev = temp;
        }
        // Return the head of the doubly linked list
        return head;
    }

    private static void print(Node head) {
        while (head != null) {
            // Print the data in the current node
            System.out.print(head.data + " ");
            // Move to the next node
            head = head.next; 
        }
        System.out.println();
    }
    
    private static Node reverseDLL(Node head) {
        // Check if the list is empty
        // or has only one node
        if (head == null || head.next == null) {
            // No change is needed;
            // return the current head
            return head; 
        }
        
         // Initialize a pointer to
         // the previous node        
        Node prev = null;
        
        // Initialize a pointer to
        // the current node
        Node current = head;
        
        // Traverse the linked list
        while (current != null) {
            
            // Store a reference to
            // the previous node
            prev = current.back;
            
            // Swap the previous and
            // next pointers
            current.back = current.next;
            
            // This step reverses the links
            current.next = prev;
            
            // Move to the next node
            // in the orignal list
            
            current = current.back;
        }

        // The final node in the original list
        // becomes the new head after reversal
        return prev.back;
    }

    

    public static void main(String[] args) {
        int[] arr = {12, 5, 6, 8, 4};
        // Convert the array to a doubly linked list
        Node head = convertArr2DLL(arr);

        // Print the doubly linked list
        System.out.println(“Doubly Linked List Initially:  “);
        print(head);

        System.out.println("Doubly Linked List After Reversing :");

        head = reverseDLL(head);
        print(head);

    }
}


class Node:
    def __init__(self, data, next_node=None, back_node=None):
        # Data stored in the node
        self.data = data
        # Reference to the next node
        # in the list (forward direction)
        self.next = next_node
        # Reference to the previous node
        # in the list (backward direction)
        self.back = back_node

def convert_arr_to_dll(arr):
    # Create the head node with
    # the first element of the array
    head = Node(arr[0])
    # Initialize 'prev' to the head node
    prev = head

    for i in range(1, len(arr)):
        # Create a new node with data from the
        # array and set its 'back' pointer
        # to the previous node
        temp = Node(arr[i], None, prev)
        
        # Update the 'next' pointer of the
        # previous node to point to the new node
        prev.next = temp
        # Move 'prev' to the newly created 
        # node for the next iteration
        prev = temp

    # Return the head of the doubly linked list
    return head

def print_dll(head):
    while head is not None:
        # Print the data in the current node
        print(head.data, end=" ")
        # Move to the next node
        head = head.next
    print()

def reverse_dll(head):
    # Check if the list is empty
    # or has only one node
    if head is None or head.next is None:
        # No change is needed;
        # return the current head
        return head
    
    # Initialize a pointer to
    # the previous node
    prev = None  
    
    # Initialize a pointer
    # to the current node
    current = head  

    # Traverse the linked list
    while current is not None:
        
        # Store a reference to
        # the previous node
        prev = current.back 

        # Swap the previous and next pointers
        current.back = current.next
        
         # This step reverses the links
        current.next = prev 
        
        # Move to the next node
        # in the original list
        current = current.back  

    # The final node in the original list
    # becomes the new head after reversal
    return prev.back

# Example usage:
arr = [12, 5, 6, 8, 4]
# Convert the array to a
# doubly linked list
head = convert_arr_to_dll(arr)
# Print the doubly linked list
print('Doubly Linked List Initially:  ')
print_dll(head)

print('Doubly Linked List After Reversing :')

# Reverse the doubly linked list
head = reverse_dll(head)
# Print the reversed doubly linked list
print_dll(head)


// Define the Node class for a doubly linked list
class Node {
    constructor(data, next, back) {
        this.data = data;
        this.next = next;
        this.back = back;
    }
}

// Function to convert an array
// to a doubly linked list
function convertArr2DLL(arr) {
    // Create the head node with 
    // the first element of the array
    let head = new Node(arr[0]);
    // Initialize 'prev' to the head node
    let prev = head;

    for (let i = 1; i < arr.length; i++) {
        // Create a new node with data from
        // the array and set its 'back' pointer
        // to the previous node
        let temp = new Node(arr[i], null, prev);
        // Update the 'next' pointer of the
        // previous node to point to the new node
        prev.next = temp;
        // Move 'prev' to the newly created
        // node for the next iteration
        prev = temp;
    }
    // Return the head of the
    // doubly linked list
    return head;
}

// Function to print the elements
// of the doubly linked list
function print(head) {
    while (head !== null) {
        // Print the data in the current node
        console.log(head.data + " ");
        // Move to the next node
        head = head.next;
    }
    console.log();
}

// Function to reverse a doubly linked list
function reverseDLL(head) {
    // Check if the list is empty
    // or has only one node
    if (head === null || head.next === null) {
        // No change is needed;
        // return the current head
        return head;
    }
    
    // Initialize a pointer to
    // the previous node
    let prev = null; 
    
    // Initialize a pointer
    // to the current node
    let current = head; 

    // Traverse the linked list
    while (current !== null) {
        // Store a reference to
        // the previous node
        prev = current.prev;

        // Swap the previous
        // and next pointers
        current.prev = current.next;
        
         // This step reverses the links
        current.next = prev;

        // Move to the next node
        // in the original list
        current = current.prev; 
    }

    // The final node in the original
    // list becomes the new head after reversal
    return prev.prev;
}

const arr = [12, 5, 6, 8, 4];
// Convert the array to a doubly linked list
let head = convertArr2DLL(arr);
// Print the doubly linked list
console.log("Doubly Linked List Initially:  ");
print(head);

console.log("Doubly Linked List After Reversing :");

head = reverseDLL(head);
print(head);

Output: Doubly Linked List Initially: 12 5 6 8 4 Doubly Linked List After Reversing : 4 8 6 5 12

Complexity Analysis

Time Complexity : O(N) We only have to traverse the doubly linked list once, hence our time complexity is O(N).

Space Complexity : O(1), as the reversal is done in place.

Video Explanation