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.
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 valueat the currentnodetemp onto the stack. Move the temp to the nextnode 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 previouslink. Along with this, the forward pointer is adjusted to point to the previous node, reversing the nextlink. To prevent losing the last node in this process, we use a reference to the lastnode to retain it.
Update the currentnode’sback pointer to point to the nextnode (current->back = current->next). This step reverses the direction of the backward pointer.
Update the currentnode’snext pointer to point to the previousnode (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 secondnode in the reversed doubly linked list. To obtain the newhead of the reversed list, we simply use the backwardpointer of the lastnode, which points to the newhead.
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 headpointer to point to the newhead of the reversed list, which is stored in the lastpointer.
Finally, we return the headpointer, 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.
