Reverse a Doubly Linked List
Last Updated :
30 Mar, 2023
Given a Doubly Linked List, the task is to reverse the given Doubly Linked List.
Example:
Input:
Output:
Follow the given steps to solve the problem using the above approach:
- Traverse the linked list using a pointer
- Swap the prev and next pointers for all nodes
- At last, change the head pointer of the doubly linked list
Below is the implementation of the above approach:
C
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void reverse(struct Node** head_ref)
{
struct Node* temp = NULL;
struct Node* current = *head_ref;
while (current != NULL) {
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
if (temp != NULL)
*head_ref = temp->prev;
}
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->prev = NULL;
new_node->next = (*head_ref);
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
(*head_ref) = new_node;
}
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
int main()
{
struct Node* head = NULL;
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
printf("\n Original Linked list ");
printList(head);
reverse(&head);
printf("\n Reversed Linked list ");
printList(head);
getchar();
}
|
C++
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node* prev;
};
void reverse(Node** head_ref)
{
Node* temp = NULL;
Node* current = *head_ref;
while (current != NULL) {
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
if (temp != NULL)
*head_ref = temp->prev;
}
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->prev = NULL;
new_node->next = (*head_ref);
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
(*head_ref) = new_node;
}
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
int main()
{
Node* head = NULL;
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
cout << "Original Linked list" << endl;
printList(head);
reverse(&head);
cout << "\nReversed Linked list" << endl;
printList(head);
return 0;
}
|
Java
class LinkedList {
static Node head;
static class Node {
int data;
Node next, prev;
Node(int d)
{
data = d;
next = prev = null;
}
}
void reverse()
{
Node temp = null;
Node current = head;
while (current != null) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
if (temp != null) {
head = temp.prev;
}
}
void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.prev = null;
new_node.next = head;
if (head != null) {
head.prev = new_node;
}
head = new_node;
}
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.push(2);
list.push(4);
list.push(8);
list.push(10);
System.out.println("Original linked list ");
list.printList(head);
list.reverse();
System.out.println("");
System.out.println("The reversed Linked List is ");
list.printList(head);
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def reverse(self):
temp = None
current = self.head
while current is not None:
temp = current.prev
current.prev = current.next
current.next = temp
current = current.prev
if temp is not None:
self.head = temp.prev
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
self.head = new_node
def printList(self, node):
while(node is not None):
print(node.data, end=' ')
node = node.next
if __name__ == "__main__":
dll = DoublyLinkedList()
dll.push(2)
dll.push(4)
dll.push(8)
dll.push(10)
print("\nOriginal Linked List")
dll.printList(dll.head)
dll.reverse()
print("\nReversed Linked List")
dll.printList(dll.head)
|
C#
using System;
public class LinkedList {
static Node head;
class Node {
public int data;
public Node next, prev;
public Node(int d)
{
data = d;
next = prev = null;
}
}
void reverse()
{
Node temp = null;
Node current = head;
while (current != null) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
if (temp != null) {
head = temp.prev;
}
}
void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.prev = null;
new_node.next = head;
if (head != null) {
head.prev = new_node;
}
head = new_node;
}
void printList(Node node)
{
while (node != null) {
Console.Write(node.data + " ");
node = node.next;
}
}
public static void Main(String[] args)
{
LinkedList list = new LinkedList();
list.push(2);
list.push(4);
list.push(8);
list.push(10);
Console.WriteLine("Original linked list ");
list.printList(head);
list.reverse();
Console.WriteLine("");
Console.WriteLine("The reversed Linked List is ");
list.printList(head);
}
}
|
Javascript
var head;
class Node {
constructor(val) {
this.data = val;
this.prev = null;
this.next = null;
}
}
function reverse() {
var temp = null;
var current = head;
while (current != null) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
if (temp != null) {
head = temp.prev;
}
}
function push(new_data) {
var new_node = new Node(new_data);
new_node.prev = null;
new_node.next = head;
if (head != null) {
head.prev = new_node;
}
head = new_node;
}
function printList(node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
push(2);
push(4);
push(8);
push(10);
document.write("Original linked list <br/>");
printList(head);
reverse();
document.write("<br/>");
document.write("The reversed Linked List is <br/>");
printList(head);
|
Output
Original Linked list 10 8 4 2
Reversed Linked list 2 4 8 10
Time Complexity: O(N), where N denotes the number of nodes in the doubly linked list.
Auxiliary Space: O(1)
We can also swap data instead of pointers to reverse the Doubly Linked List. Method used for reversing array can be used to swap data. Swapping data can be costly compared to pointers if the size of the data item(s) is more.
Reverse a Doubly Linked List using Stack:
Push the node’s data into the stack while traversing the doubly linked list, then pop out the elements from the stack and copy the value to the nodes of the linked list by again traversing it
Follow the given steps to solve the problem using the above approach:
- Traverse the whole Linked List and Keep pushing the node’s data into the stack
- Then keep popping the elements out of the stack and updating the Doubly Linked List
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
struct LinkedList {
struct Node {
int data;
Node *next, *prev;
Node(int d)
{
data = d;
next = prev = NULL;
}
};
Node* head = NULL;
void reverse()
{
stack<int> st;
Node* temp = head;
while (temp != NULL) {
st.push(temp->data);
temp = temp->next;
}
temp = head;
while (temp != NULL) {
temp->data = st.top();
st.pop();
temp = temp->next;
}
}
void Push(int new_data)
{
Node* new_node = new Node(new_data);
new_node->prev = NULL;
new_node->next = head;
if (head != NULL) {
head->prev = new_node;
}
head = new_node;
}
void printList(Node* node)
{
while (node) {
cout << node->data << " ";
node = node->next;
}
}
};
int main()
{
LinkedList list;
list.Push(2);
list.Push(4);
list.Push(8);
list.Push(10);
cout << "Original linked list " << endl;
list.printList(list.head);
list.reverse();
cout << endl;
cout << "The reversed Linked List is " << endl;
list.printList(list.head);
}
|
Java
import java.util.*;
class LinkedList {
static Node head;
static class Node {
int data;
Node next, prev;
Node(int d)
{
data = d;
next = prev = null;
}
}
void reverse()
{
Stack<Integer> stack = new Stack<>();
Node temp = head;
while (temp != null) {
stack.push(temp.data);
temp = temp.next;
}
temp = head;
while (temp != null) {
temp.data = stack.pop();
temp = temp.next;
}
}
void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.prev = null;
new_node.next = head;
if (head != null) {
head.prev = new_node;
}
head = new_node;
}
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.push(2);
list.push(4);
list.push(8);
list.push(10);
System.out.println("Original linked list ");
list.printList(head);
list.reverse();
System.out.println("");
System.out.println("The reversed Linked List is ");
list.printList(head);
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def reverseUsingStacks(self):
stack = []
temp = self.head
while temp is not None:
stack.append(temp.data)
temp = temp.next
temp = self.head
while temp is not None:
temp.data = stack.pop()
temp = temp.next
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
self.head = new_node
def printList(self, node):
while(node is not None):
print(node.data)
node = node. next
if __name__ == "__main__":
dll = DoublyLinkedList()
dll.push(2)
dll.push(4)
dll.push(8)
dll.push(10)
print("original doubly-linked list")
dll.printList(dll.head)
dll.reverseUsingStacks()
print(" reversed doubly-linked list")
dll.printList(dll.head)
|
C#
using System;
using System.Collections;
using System.Collections.Generic;
class LinkedList {
public static Node head;
public class Node {
public int data;
public Node next, prev;
public Node(int d)
{
data = d;
next = prev = null;
}
}
public void reverse()
{
Stack stack = new Stack();
Node temp = head;
while (temp != null) {
stack.Push(temp.data);
temp = temp.next;
}
temp = head;
while (temp != null) {
temp.data = (int)stack.Pop();
temp = temp.next;
}
}
public void Push(int new_data)
{
Node new_node = new Node(new_data);
new_node.prev = null;
new_node.next = head;
if (head != null) {
head.prev = new_node;
}
head = new_node;
}
public void printList(Node node)
{
while (node != null) {
Console.Write(node.data + " ");
node = node.next;
}
}
public static void Main(string[] args)
{
LinkedList list = new LinkedList();
list.Push(2);
list.Push(4);
list.Push(8);
list.Push(10);
Console.WriteLine("Original linked list ");
list.printList(head);
list.reverse();
Console.WriteLine("");
Console.WriteLine("The reversed Linked List is ");
list.printList(head);
}
}
|
Javascript
class Node
{
constructor(d)
{
this.data = d;
this.next = this.prev = null;
}
}
let head;
function reverse()
{
let stack = [];
let temp = head;
while (temp != null)
{
stack.push(temp.data);
temp = temp.next;
}
temp = head;
while (temp != null)
{
temp.data = stack.pop();
temp = temp.next;
}
}
function push(new_data)
{
let new_node = new Node(new_data);
new_node.prev = null;
new_node.next = head;
if (head != null) {
head.prev = new_node;
}
head = new_node;
}
function printList(node)
{
while (node != null)
{
document.write(node.data + " ");
node = node.next;
}
}
push(2);
push(4);
push(8);
push(10);
document.write("Original linked list <br>");
printList(head);
reverse();
document.write("<br>");
document.write("The reversed Linked List is <br>");
printList(head);
|
Output
Original linked list
10 8 4 2
The reversed Linked List is
2 4 8 10
Time Complexity: O(N)
Auxiliary Space: O(N)
To reverse a doubly linked list, we can follow the below algorithm:
Check if the head of the linked list is null or the next node is null. If yes, return the head of the list.
Initialize three pointers – current pointing to the head of the list, prev to null and next to null.
Traverse the linked list by moving the current pointer to the next node, and for each node, set its next pointer to point to the previous node and its prev pointer to point to the next node.
Once the traversal is complete, set the head of the list to point to the last node of the original linked list (which is now the first node of the reversed list).
Return the new head of the list.
Algorithmic Steps:
Step 1 : Create a function to reverse the linked list, which takes the head node as input.
step 2 : Initialize three pointers: prevNode to NULL, currentNode to the head node, and nextNode to NULL.
Step 3 : Traverse the linked list using a while loop until the currentNode pointer is not NULL.
Step 4 : Inside the loop, assign nextNode as the next node of the currentNode using the next pointer.
Step 5 : Set the next pointer of the currentNode to prevNode, effectively reversing the pointer direction of the currentNode.
Step 6 : Update prevNode to the currentNode.
Step 7 : Update currentNode to the nextNode.
Step 8 :Finally, set the head node to prevNode and return it.
In this algorithm, we first check if the linked list is empty or has only one node. If yes, we return the head of the list. Then we initialize three pointers – current, prev and next – to null, the head of the list and null, respectively. Then, we traverse the linked list, setting the next and prev pointers of each node to point to the previous and next nodes, respectively. Finally, we set the head of the list to the last node of the original linked list (which is now the first node of the reversed list) and return the new head.
C++
#include <iostream>
struct Node {
int data;
Node* prev;
Node* next;
};
void reverse(Node** head_ref) {
Node* current = *head_ref;
Node* temp = NULL;
while (current != NULL) {
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
if (temp != NULL) {
*head_ref = temp->prev;
}
}
void printList(Node* node) {
while (node != NULL) {
std::cout << node->data << " ";
node = node->next;
}
}
int main() {
Node* head = NULL;
Node* second = NULL;
Node* third = NULL;
head = new Node();
second = new Node();
third = new Node();
head->data = 1;
head->prev = NULL;
head->next = second;
second->data = 2;
second->prev = head;
second->next = third;
third->data = 3;
third->prev = second;
third->next = NULL;
std::cout << "Original List: ";
printList(head);
reverse(&head);
std::cout << "\nReversed List: ";
printList(head);
return 0;
}
|
Java
class Node {
int data;
Node prev;
Node next;
}
class Main {
static void reverse(Node[] head_ref)
{
Node current = head_ref[0];
Node temp = null;
while (current != null) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
if (temp != null) {
head_ref[0] = temp.prev;
}
}
static void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args)
{
Node head = null;
Node second = null;
Node third = null;
head = new Node();
second = new Node();
third = new Node();
head.data = 1;
head.prev = null;
head.next = second;
second.data = 2;
second.prev = head;
second.next = third;
third.data = 3;
third.prev = second;
third.next = null;
System.out.print("Original List: ");
printList(head);
Node[] head_ref = new Node[1];
head_ref[0] = head;
reverse(head_ref);
head = head_ref[0];
System.out.print("\nReversed List: ");
printList(head);
}
}
|
Python3
class Node:
def __init__(self):
self.data = 0
self.prev = None
self.next = None
def reverse(head_ref):
current = head_ref
temp = None
while current != None:
temp = current.prev
current.prev = current.next
current.next = temp
current = current.prev
if temp != None:
head_ref = temp.prev
return head_ref
def printList(node):
while node != None:
print(node.data, end=" ")
node = node.next
head = Node()
second = Node()
third = Node()
head.data = 1
head.prev = None
head.next = second
second.data = 2
second.prev = head
second.next = third
third.data = 3
third.prev = second
third.next = None
print("Original List: ", end="")
printList(head)
head = reverse(head)
print("\nReversed List: ", end="")
printList(head)
|
C#
using System;
public class Node {
public int data;
public Node prev;
public Node next;
}
public class Program {
static void reverse(ref Node head) {
Node current = head;
Node temp = null;
while (current != null) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
if (temp != null) {
head = temp.prev;
}
}
static void printList(Node node) {
while (node != null) {
Console.Write(node.data + " ");
node = node.next;
}
}
public static void Main(string[] args) {
Node head = null;
Node second = null;
Node third = null;
head = new Node();
second = new Node();
third = new Node();
head.data = 1;
head.prev = null;
head.next = second;
second.data = 2;
second.prev = head;
second.next = third;
third.data = 3;
third.prev = second;
third.next = null;
Console.Write("Original List: ");
printList(head);
reverse(ref head);
Console.Write("\nReversed List: ");
printList(head);
}
}
|
Javascript
class Node {
constructor() {
this.data = 0;
this.prev = null;
this.next = null;
}
}
function reverse(head_ref) {
let current = head_ref;
let temp = null;
while (current != null) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
if (temp != null) {
head_ref = temp.prev;
}
return head_ref;
}
function printList(node) {
while (node != null) {
console.log(node.data + " ");
node = node.next;
}
}
let head = new Node();
let second = new Node();
let third = new Node();
head.data = 1;
head.prev = null;
head.next = second;
second.data = 2;
second.prev = head;
second.next = third;
third.data = 3;
third.prev = second;
third.next = null;
console.log("Original List: ")
printList(head)
head = reverse(head)
console.log("\nReversed List: ")
printList(head)
|
Output
Original List: 1 2 3
Reversed List: 3 2 1
Time and Space complexities:
reverse(Node** head_ref): This function reverses the doubly linked list. The time complexity of this function is O(n), where n is the number of nodes in the list. This is because the function visits each node once and performs a constant amount of work on each node. The space complexity of this function is O(1), as it uses a constant amount of extra memory regardless of the size of the input.
printList(Node* node): This function prints the contents of the doubly linked list. The time complexity of this function is O(n), where n is the number of nodes in the list. This is because the function visits each node once and performs a constant amount of work on each node. The space complexity of this function is O(1), as it uses a constant amount of extra memory regardless of the size of the input.
main(): This function creates a doubly linked list and then reverses it using the reverse() function. The time complexity of this function is O(n), where n is the number of nodes in the list. This is because the function calls the reverse() function, which has a time complexity of O(n), and also calls the printList() function twice, each of which has a time complexity of O(n). The space complexity of this function is O(n), as it creates a doubly linked list with n nodes and uses a constant amount of extra memory for the pointers head, second, and third.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...