Reverse a Doubly Linked List
Last Updated :
28 Aug, 2024
Given a Doubly Linked List, the task is to reverse the Doubly Linked List.
Examples:
Input: Doubly Linked List = 1 <-> 2 <-> 3 -> NULL
Doubly Linked List
Output: Reversed Doubly Linked List = 3 <-> 2 <-> 1 -> NULL
Reversed Doubly Linked List
Input: Doubly Linked List = 1 ->NULL
Output: Reversed Doubly Linked List = 1 ->NULL
[Naive Approach] Using Recursion – O(n) Time and O(n) Space
The idea is to use recursion to reverse the links in the doubly linked list. The recursive function will traverse the list and reverse the links while backtracking.
Step-by-Step algorithm:
- Recursively traverse the doubly linked list until it reaches the last node.
- While backtracking, reverse the links between the nodes. To reverse the links:
- Change the next pointer of the current node to point to its previous node.
- Change the prev pointer of the current node to point to its next node.
- Adjust the head of the doubly linked list to point to the last node.
Below is the implementation of the above approach:
C++
// C++ program to reverse a
//doubly linked list using recursion
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *next, *prev;
Node(int val) {
data = val;
next = nullptr;
prev = nullptr;
}
};
// Recursive function to reverse a doubly linked list
Node *reverse(Node *curr) {
// Base case: if the list is empty or we
// reach the end of the list
if (curr == NULL)
return NULL;
// Swap the next and prev pointers
Node *temp = curr->prev;
curr->prev = curr->next;
curr->next = temp;
// If the previous node (after swap) is null,
// this is the new head
if (curr->prev == nullptr)
return curr;
// Recurse for the next node
return reverse(curr->prev);
}
void printList(Node *node) {
while (node != nullptr) {
cout << node->data << " ";
node = node->next;
}
}
int main() {
// Create a hard-coded doubly linked list:
// 1 <-> 2 <-> 3 <-> 4
Node *head = new Node(1);
head->next = new Node(2);
head->next->prev = head;
head->next->next = new Node(3);
head->next->next->prev = head->next;
head->next->next->next = new Node(4);
head->next->next->next->prev = head->next->next;
cout << "Original Linked list" << endl;
printList(head);
head = reverse(head);
cout << "\nReversed Linked list" << endl;
printList(head);
return 0;
}
// C program to reverse a doubly
//linked list using recursion
#include <stdio.h>
struct Node {
int data;
struct Node *next;
struct Node *prev;
};
// Recursive function to reverse a doubly linked list
struct Node *reverse(struct Node *curr) {
// Base case: If the list is empty or we
// reach the end of the list
if (curr == NULL) return NULL;
// Swap the next and prev pointers
struct Node *temp = curr->prev;
curr->prev = curr->next;
curr->next = temp;
// If the previous node (after swap) is NULL
// his is the new head
if (curr->prev == NULL) return curr;
// Recurse for the next node
return reverse(curr->prev);
}
void printList(struct Node *node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
struct Node *createNode(int new_data) {
struct Node *new_node =
(struct Node *)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = NULL;
new_node->prev = NULL;
return new_node;
}
int main() {
// Create a hrad-coded doubly linked list:
// 1 <-> 2 <-> 3 <-> 4
struct Node *head = createNode(1);
head->next = createNode(2);
head->next->prev = head;
head->next->next = createNode(3);
head->next->next->prev = head->next;
head->next->next->next = createNode(4);
head->next->next->next->prev = head->next->next;
printf("Original Linked list\n");
printList(head);
head = reverse(head);
printf("Reversed Linked list\n");
printList(head);
return 0;
}
// Java program to reverse a
// doubly linked list using recursion
class GfG {
static Node head;
static class Node {
int data;
Node next, prev;
Node(int d) {
data = d;
next = prev = null;
}
}
// Recursive function to reverse a doubly linked list
static Node reverse(Node curr) {
// Base case: If list is empty or we
// reach the end of the list
if (curr == null)
return null;
// Swap the next and prev pointers
Node temp = curr.prev;
curr.prev = curr.next;
curr.next = temp;
// If prev is null after swap, this is the new head
if (curr.prev == null) {
return curr;
}
// Recurse for the next node
return reverse(curr.prev);
}
static void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
System.out.println();
}
public static void main(String[] args) {
// Manually create a doubly linked list:
// 1 <-> 2 <-> 3 <-> 4
head = new Node(1);
head.next = new Node(2);
head.next.prev = head;
head.next.next = new Node(3);
head.next.next.prev = head.next;
head.next.next.next = new Node(4);
head.next.next.next.prev = head.next.next;
System.out.println("Original linked list:");
printList(head);
// Reverse the doubly linked list
head = reverse(head);
System.out.println("Reversed linked list:");
printList(head);
}
}
# Python program to reverse a doubly
# linked list using recursion
class Node:
def __init__(self, val):
self.data = val
self.next = None
self.prev = None
# Recursive function to reverse a doubly linked list
def reverse(curr):
# Base case: if the list is empty or we reach the end of the list
if curr is None:
return None
# Swap the next and prev pointers
temp = curr.prev
curr.prev = curr.next
curr.next = temp
# If the previous node (after swap) is null, this is the new head
if curr.prev is None:
return curr
# Recurse for the next node
return reverse(curr.prev)
def print_list(node):
while node is not None:
print(node.data, end=" ")
node = node.next
print()
if __name__ == "__main__":
# Create a hard-coded doubly linked list:
# 1 <-> 2 <-> 3 <-> 4
head = Node(1)
head.next = Node(2)
head.next.prev = head
head.next.next = Node(3)
head.next.next.prev = head.next
head.next.next.next = Node(4)
head.next.next.next.prev = head.next.next
print("Original Linked list")
print_list(head)
head = reverse(head)
print("\nReversed Linked list")
print_list(head)
// C# program to reverse a doubly
// linked list using recursion
using System;
public class Node {
public int Data;
public Node Next;
public Node Prev;
public Node(int val) {
Data = val;
Next = null;
Prev = null;
}
}
class GfG {
// Recursive function to reverse a doubly linked list
static Node Reverse(Node curr) {
// Base case: if the list is empty or we reach the
// end of the list
if (curr == null)
return null;
// Swap the next and prev pointers
Node temp = curr.Prev;
curr.Prev = curr.Next;
curr.Next = temp;
// If the previous node (after swap) is null,
// this is the new head
if (curr.Prev == null)
return curr;
// Recurse for the next node
return Reverse(curr.Prev);
}
// Function to print the linked list
static void PrintList(Node node) {
while (node != null) {
Console.Write(node.Data + " ");
node = node.Next;
}
Console.WriteLine();
}
static void Main() {
// Create a hard-coded doubly linked list:
// 1 <-> 2 <-> 3 <-> 4
Node head = new Node(1);
head.Next = new Node(2);
head.Next.Prev = head;
head.Next.Next = new Node(3);
head.Next.Next.Prev = head.Next;
head.Next.Next.Next = new Node(4);
head.Next.Next.Next.Prev = head.Next.Next;
Console.WriteLine("Original Linked list");
PrintList(head);
head = Reverse(head);
Console.WriteLine("Reversed Linked list");
PrintList(head);
}
}
// Javascript program to reverse a doubly
// linked list using recursion
class Node {
constructor(val) {
this.data = val;
this.next = null;
this.prev = null;
}
}
// Recursive function to reverse a doubly linked list
function reverse(curr) {
// Base case: if the list is empty or we reach the end of the list
if (curr === null) {
return null;
}
// Swap the next and prev pointers
const temp = curr.prev;
curr.prev = curr.next;
curr.next = temp;
// If the previous node (after swap) is null, this is the new head
if (curr.prev === null) {
return curr;
}
// Recurse for the next node
return reverse(curr.prev);
}
// Function to print the linked list
function printList(node) {
let output = '';
while (node !== null) {
output += node.data + ' ';
node = node.next;
}
console.log(output.trim());
}
// Create a hard-coded doubly linked list:
// 1 <-> 2 <-> 3 <-> 4
const head = new Node(1);
head.next = new Node(2);
head.next.prev = head;
head.next.next = new Node(3);
head.next.next.prev = head.next;
head.next.next.next = new Node(4);
head.next.next.next.prev = head.next.next;
console.log("Original Linked list:");
printList(head);
const reversedHead = reverse(head);
console.log("\nReversed Linked list:");
printList(reversedHead);
OutputOriginal Linked list
1 2 3 4
Reversed Linked list
4 3 2 1
Time Complexity: O(n), where n are the number of nodes in doubly linked list.
Auxiliary Space: O(n)
[Expected Approach] Using Two Pointers – O(n) Time and O(1) Space
The idea is to reverse doubly linked list using two pointers for traversing through the list and swapping the next and previous pointers of every two consecutive nodes.
Step-by-step algorithm:
- Initially, prevNode is set to NULL and currNode starts at the head.
- As the list is traversed,
- Update prevNode to currNode’s prev, prevNode = currNode->prev.
- Update currNode’s prev pointer to its next node, currNode->prev = currNode->next.
- Update currNode’s next pointer to prevNode, currNode->next = prevNode.
- Move currNode to the next node, currNode = currNode->prev.
- After traversing all the nodes, prevNode will point to the second node of the reversed list, so update the previous pointer of prevNode as the new head of the linked list, head = prevNode->prev and return it.
Working of the above algorithm:
Below is the implementation of the above approach:
C++
// C++ code to Reverse a doubly linked list,
// using two pointers
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *next;
Node *prev;
Node(int new_data) {
data = new_data;
next = NULL;
prev = NULL;
}
};
// Function to reverse a doubly linked list
Node *reverse(Node *head) {
// If the list is empty or has only one node,
// return the head as is
if (head == nullptr || head->next == nullptr)
return head;
Node *prevNode = NULL;
Node *currNode = head;
// Traverse the list and reverse the links
while (currNode != nullptr) {
// Swap the next and prev pointers
prevNode = currNode->prev;
currNode->prev = currNode->next;
currNode->next = prevNode;
// Move to the next node in the original list
// (which is now previous due to reversal)
currNode = currNode->prev;
}
// The final node in the original list
// becomes the new head after reversal
return prevNode->prev;
}
void printList(Node *node) {
while (node != nullptr) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
int main() {
// Create a doubly linked list:
// 1 <-> 2 <-> 3 <-> 4
Node *head = new Node(1);
head->next = new Node(2);
head->next->prev = head;
head->next->next = new Node(3);
head->next->next->prev = head->next;
head->next->next->next = new Node(4);
head->next->next->next->prev = head->next->next;
cout << "Original Doubly Linked List" << endl;
printList(head);
head = reverse(head);
cout << "Reversed Doubly Linked List" << endl;
printList(head);
return 0;
}
// C code to Reverse a doubly linked list,
// using two pointers
#include <stdio.h>
struct Node {
int data;
struct Node *next;
struct Node *prev;
};
// Function to reverse a Doubly Linked List using two pointers
struct Node *reverse(struct Node *head) {
if (head == NULL || head->next == NULL)
return head;
struct Node *prevNode = NULL;
struct Node *currNode = head;
// Traverse the list and reverse the links
while (currNode != NULL) {
// Swap the next and prev pointers
prevNode = currNode->prev;
currNode->prev = currNode->next;
currNode->next = prevNode;
// Move to the next node in the original list
// (which is now previous due to reversal)
currNode = currNode->prev;
}
// The final node processed will be the new head
// Fix head pointer
if (prevNode != NULL)
head = prevNode->prev;
return head;
}
void printList(struct Node *node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
struct Node *createNode(int new_data){
struct Node *new_node =
(struct Node *)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = NULL;
new_node->prev = NULL;
return new_node;
}
int main() {
// Create a hard-coded doubly linked list:
// 1 <-> 2 <-> 3 <-> 4
struct Node *head = createNode(1);
head->next = createNode(2);
head->next->prev = head;
head->next->next = createNode(3);
head->next->next->prev = head->next;
head->next->next->next = createNode(4);
head->next->next->next->prev = head->next->next;
printf("Original Doubly Linked List\n");
printList(head);
head = reverse(head);
printf("Reversed Doubly Linked List\n");
printList(head);
return 0;
}
// Java code to Reverse a doubly linked list,
// using two pointers
class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
public class GfG {
// Function to reverse a Doubly Linked List using two
// pointers
static Node reverse(Node head) {
if (head == null || head.next == null) {
return head;
}
Node currNode = head;
Node prevNode = null;
// Traverse the list and reverse the links
while (currNode != null) {
// Swap the next and prev pointers
prevNode = currNode.prev;
currNode.prev = currNode.next;
currNode.next = prevNode;
// Move to the next node in the original list
// (which is now previous due to reversal)
currNode = currNode.prev;
}
// Update head of Doubly Linked List
head = prevNode.prev;
return head;
}
static void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
System.out.println();
}
public static void main(String[] args) {
// Create a doubly linked list:
// 1 <-> 2 <-> 3 <-> 4
Node head = new Node(1);
head.next = new Node(2);
head.next.prev = head;
head.next.next = new Node(3);
head.next.next.prev = head.next;
head.next.next.next = new Node(4);
head.next.next.next.prev = head.next.next;
System.out.println("Original Doubly Linked List");
printList(head);
head = reverse(head);
System.out.println("Reversed Doubly Linked List");
printList(head);
}
}
# Python code to Reverse a doubly linked list,
# using two pointers
class Node:
def __init__(self, new_data):
self.data = new_data
self.next = None
self.prev = None
def reverse(head):
# If the list is empty or has only one node,
# return the head as is
if head is None or head.next is None:
return head
prevNode = None
currNode = head
# Traverse the list and reverse the links
while currNode is not None:
# Swap the next and prev pointers
prevNode = currNode.prev
currNode.prev = currNode.next
currNode.next = prevNode
# Move to the next node in the original list
# (which is now previous due to reversal)
currNode = currNode.prev
# The final node in the original list
# becomes the new head after reversal
return prevNode.prev
def printList(node):
while node is not None:
print(node.data, end=" ")
node = node.next
print()
if __name__ == "__main__":
# Create a doubly linked list:
# 1 <-> 2 <-> 3 <-> 4
head = Node(1)
head.next = Node(2)
head.next.prev = head
head.next.next = Node(3)
head.next.next.prev = head.next
head.next.next.next = Node(4)
head.next.next.next.prev = head.next.next
print("Original Doubly Linked List")
printList(head)
head = reverse(head)
print("Reversed Doubly Linked List")
printList(head)
// C# code to Reverse a doubly linked list,
// using two pointers
using System;
class Node {
public int Data;
public Node Next;
public Node Prev;
public Node(int newData) {
Data = newData;
Next = null;
Prev = null;
}
}
class GfG {
// Function to reverse a doubly linked list
static Node Reverse(Node head) {
// If the list is empty or has only one node,
// return the head as is
if (head == null || head.Next == null)
return head;
Node prevNode = null;
Node currNode = head;
// Traverse the list and reverse the links
while (currNode != null) {
// Swap the next and prev pointers
prevNode = currNode.Prev;
currNode.Prev = currNode.Next;
currNode.Next = prevNode;
// Move to the next node in the original list
// (which is now previous due to reversal)
currNode = currNode.Prev;
}
// The final node in the original list
// becomes the new head after reversal
return prevNode.Prev;
}
static void PrintList(Node node) {
while (node != null) {
Console.Write(node.Data + " ");
node = node.Next;
}
Console.WriteLine();
}
public static void Main() {
// Create a doubly linked list:
// 1 <-> 2 <-> 3 <-> 4
Node head = new Node(1);
head.Next = new Node(2);
head.Next.Prev = head;
head.Next.Next = new Node(3);
head.Next.Next.Prev = head.Next;
head.Next.Next.Next = new Node(4);
head.Next.Next.Next.Prev = head.Next.Next;
Console.WriteLine("Original Doubly Linked List");
PrintList(head);
head = Reverse(head);
Console.WriteLine("Reversed Doubly Linked List");
PrintList(head);
}
}
// Javascript code to Reverse a doubly linked list,
// using two pointers
class Node {
constructor(new_data) {
this.data = new_data;
this.next = null;
this.prev = null;
}
}
// Function to reverse a doubly linked list
function reverse(head) {
// If the list is empty or has only one node,
// return the head as is
if (head === null || head.next === null)
return head;
let prevNode = null;
let currNode = head;
// Traverse the list and reverse the links
while (currNode !== null) {
// Swap the next and prev pointers
prevNode = currNode.prev;
currNode.prev = currNode.next;
currNode.next = prevNode;
// Move to the next node in the original list
// (which is now previous due to reversal)
currNode = currNode.prev;
}
// The final node in the original list
// becomes the new head after reversal
return prevNode.prev;
}
function printList(node) {
let output = "";
while (node !== null) {
output += node.data + " ";
node = node.next;
}
console.log(output);
}
// Create a doubly linked list:
// 1 <-> 2 <-> 3 <-> 4
let head = new Node(1);
head.next = new Node(2);
head.next.prev = head;
head.next.next = new Node(3);
head.next.next.prev = head.next;
head.next.next.next = new Node(4);
head.next.next.next.prev = head.next.next;
console.log("Original Doubly Linked List");
printList(head);
head = reverse(head);
console.log("Reversed Doubly Linked List");
printList(head);
OutputOriginal Doubly Linked List
1 2 3 4
Reversed Doubly Linked List
4 3 2 1
Time Complexity: O(n), where n denotes the number of nodes in the doubly linked list.
Auxiliary Space: O(1)
Similar Reads
Doubly Linked List meaning in DSA
A doubly linked list is a special type of linked list in which each node contains a pointer to the previous node as well as the next node in the structure. Characteristics of the Doubly Linked List: The characteristics of a doubly linked list are as follows: Dynamic size: The size of a doubly linked
3 min read
Doubly Linked List Tutorial
A doubly linked list is a more complex data structure than a singly linked list, but it offers several advantages. The main advantage of a doubly linked list is that it allows for efficient traversal of the list in both directions. This is because each node in the list contains a pointer to the prev
9 min read
Difference between Singly linked list and Doubly linked list
Introduction to Singly linked list : A singly linked list is a set of nodes where each node has two fields 'data' and 'link'. The 'data' field stores actual piece of information and 'link' field is used to point to next node. Basically the 'link' field stores the address of the next node. Introduct
2 min read
Applications, Advantages and Disadvantages of Doubly Linked List
Doubly linked list is a type of linked list in which nodes contains information and two pointers i.e. left pointer and right pointer. The left pointer in the doubly linked list points to the previous node and the right pointer points to the next node in the linked list. The first node of the doubly
4 min read
Operations on Doubly Linked
Operations of Doubly Linked List with Implementation
A Doubly Linked List (DLL) contains an extra pointer, typically called the previous pointer, together with the next pointer and data which are there in a singly linked list. Below are operations on the given DLL: Add a node at the front of DLL: The new node is always added before the head of the giv
15+ min read
Insertion in a Doubly Linked List
Inserting a new node in a doubly linked list is very similar to inserting new node in linked list. There is a little extra work required to maintain the link of the previous node. In this article, we will learn about different ways to insert a node in a doubly linked list. Table of Content Insertion
6 min read
Search an element in a Doubly Linked List
Given a Doubly linked list(DLL) containing n nodes and an integer x, the task is to find the position of the integer x in the doubly linked list. If no such position found then print -1. Examples: Input: Linked List = 18 <-> 15 <-> 8 <-> 9 <-> 14, x = 8 Output: 3 Explanation:
7 min read
Deletion in a Doubly Linked List
Deleting a node in a doubly linked list is very similar to deleting a node in a singly linked list. However, there is a little extra work required to maintain the links of both the previous and next nodes. In this article, we will learn about different ways to delete a node in a doubly linked list.
15+ min read
Delete a Doubly Linked List node at a given position
Given a doubly linked list and a position pos, the task is to delete the node at the given position from the beginning of Doubly Linked List. Input: LinkedList: 1<->2<->3, pos = 2Output: LinkedList: 1<->3 Input: LinkedList: 1<->2<->3, pos = 1Output: LinkedList: 2<-
9 min read
Doubly Linked List in Different Languages
How to Create a Doubly Linked List in C?
A doubly linked list is a type of linked list in which each node contains a pointer to both the next node and the previous node. This allows traversal in both forward and backward directions. Each node in a doubly linked list stores data, a pointer to the next node, and a pointer to the previous nod
4 min read
Introduction to Doubly Linked Lists in Java
Doubly linked list is a data structure that has reference to both the previous and next nodes in the list. It provides simplicity to traverse, insert and delete the nodes in both directions in a list. In a doubly linked list, each node contains three data members: data: The data stored in the nodene
11 min read
Doubly Linked List in Python
[mtouchquiz 2151]
1 min read
Implementation of Doubly Linked List in JavaScript
This article will demonstrate the Implementation of Doubly Linked List In JavaScript. A doubly linked list (DLL) is a special type of linked list in which each node contains a pointer to the previous node as well as the next node of the linked list. Doubly Linked List in JavaScriptTo create we have
4 min read