Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach1: Using Stack
3.1.
Algorithm
3.2.
Implementation
3.3.
C++
3.4.
C
3.5.
Python
3.6.
Java
3.7.
C#
3.8.
JavaScript
3.9.
Complexity Analysis
4.
Approach 2: Using Iteration with constant space
4.1.
Algorithm
4.2.
Implementation
4.3.
C++
4.4.
C
4.5.
Java
4.6.
Python
4.7.
JavaScript
4.8.
C#
4.9.
Complexity Analysis
5.
Method 3: Recursion with constant space
5.1.
Algorithm
5.2.
Implementation
5.3.
C++
5.4.
C
5.5.
Java
5.6.
Python
5.7.
C#
5.8.
JavaScript
5.9.
Complexity Analysis
6.
Frequently Asked Question
6.1.
What are the main steps involved in reversing a singly linked list?
6.2.
How many pointers are required to reverse a linked list?
6.3.
How can reversing a linked list affect its usability or performance in an application?
6.4.
Why do we need to reverse a linked list?
7.
Conclusion
Last Updated: Nov 4, 2024
Medium

Reverse a Linked List

Author Pranav Gautam
1 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Reversing a linked list is a common problem in data structures where the order of nodes is reversed, making the last node the new head. This can be achieved using iterative or recursive methods, and mastering it enhances understanding of pointers and node manipulation in linked lists.

Reverse a Linked List

In this article, we’ll learn how to reverse a linked list, a fundamental technique in data structures that involves reversing the order of nodes so that the last node becomes the head. We’ll cover both iterative and recursive methods, which help deepen understanding of pointers and linked list manipulation.

Recommended Topic, Floyds Algorithm

Problem Statement

The ‘HEAD’ pointer of a linked list is given. Return the ‘HEAD’ pointer of the reversed linked list.

Input

Enter the number of nodes in the linked list: 4
Enter the data of nodes: 1 2 3 4

Output

Reversed linked list: 4 3 2 1

Explanation

 

illustration image

Recommended: Try the Problem yourself before moving on to the Solution

Approach1: Using Stack

Stack follows the LIFO principle, which means the element that comes at the last should be shown first. That’s exactly what we want. We want to print the last node of the linked list first and so on. 

Using stack to create a reversed linked list is pretty simple. Put all the nodes of the linked list in a stack. 

stack

Then, start popping out the nodes from the stack. Set the ‘NEXT’ pointer of the current popped node to the previously popped node.

illustration image

Refer to the algorithm given below for a better understanding.

Also read - Merge sort in linked list

Algorithm

  • If the ‘HEAD’ points to NULL (means linked list is empty), then:
    • Return NULL.
  • Create a stack ‘NODE_STACK’.
  • Set a pointer, ‘CURRENT’ (node pointer to point at the current node during linked list traversal) equal to the ‘HEAD’.
  • While CURRENT -> NEXT is not equal to NULL, do:
    • Push ‘CURRENT’ into the ‘NODE_STACK’.
    • Set ‘CURRENT’ = CURRENT -> NEXT.
  • Set ‘HEAD’ equal to ‘CURRENT’ (‘CURRENT’ after the while loop, points to the last element of the linked list).
  • Initialise ‘PREVIOUS_TOP’ with ‘CURRENT’ node to store the previous top element of the stack.
  • While ‘NODE_STACK’ is not empty, do:
    • Set ‘CURRENT’ equal to the top element of the ‘NODE_STACK’.
    • Pop the top element off ‘NODE_STACK’.
    • Set PREVIOUS_TOP -> NEXT = CURRENT (Set the next pointer of the previous top of the stack equal to the current top).
    • Set ‘PREVIOUS_TOP’ equal to ‘CURRENT’.
  • Set PREVIOUS_TOP -> NEXT equal to NULL. (To represent the end of the linked list).

Implementation

  • C++
  • C
  • Python
  • Java
  • C#
  • JavaScript

C++

#include <iostream>
#include <stack>
using namespace std;

class Node {
public:
int data;
Node* next;

Node(int data) {
this->data = data;
next = NULL;
}
};

class LinkedList {
Node* head;

public:
LinkedList() {
head = NULL;
}

void printLinkedList() {
Node* current = head;
while (current) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}

void insert(int data) {
if (head == NULL) {
head = new Node(data);
return;
}
Node* current = head;
while (current->next) {
current = current->next;
}
current->next = new Node(data);
}

void reverseLinkedList() {
stack<Node*> nodeStack;
Node* current = head;
while (current->next) {
nodeStack.push(current);
current = current->next;
}
head = current;
Node* previousTop = current;
while (!nodeStack.empty()) {
current = nodeStack.top();
nodeStack.pop();
previousTop->next = current;
previousTop = current;
}
previousTop->next = NULL;
printLinkedList();
}
};

int main() {
int totalNodes;
cout << "Enter the number of nodes in the linked list: ";
cin >> totalNodes;

cout << "Enter the data of nodes: ";
LinkedList* givenList = new LinkedList();
for (int i = 0; i < totalNodes; i++) {
int data;
cin >> data;
givenList->insert(data);
}

cout << "Reversed linked list: ";
givenList->reverseLinkedList();
}
You can also try this code with Online C++ Compiler
Run Code

C

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

void insert(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = *head;
*head = newNode;
}

void reverse(struct Node** head) {
struct Node* prev = NULL;
struct Node* current = *head;
struct Node* next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head = prev;
}

void printList(struct Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}

int main() {
struct Node* head = NULL;
int totalNodes, data;
printf("Enter the number of nodes: ");
scanf("%d", &totalNodes);

for (int i = 0; i < totalNodes; i++) {
printf("Enter node data: ");
scanf("%d", &data);
insert(&head, data);
}

printf("Reversed list: ");
reverse(&head);
printList(head);
}
You can also try this code with Online C Compiler
Run Code

Python

class Node:
def __init__(self, data):
self.data = data
self.next = None

class LinkedList:
def __init__(self):
self.head = None

def insert(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node

def reverse_linked_list(self):
stack = []
current = self.head
while current.next:
stack.append(current)
current = current.next
self.head = current
previous_top = current
while stack:
current = stack.pop()
previous_top.next = current
previous_top = current
previous_top.next = None
self.print_linked_list()

def print_linked_list(self):
current = self.head
while current:
print(current.data, end=" ")
current = current.next
print()

# Driver code
if __name__ == "__main__":
linked_list = LinkedList()
total_nodes = int(input("Enter the number of nodes: "))
print("Enter node data:")
for _ in range(total_nodes):
data = int(input())
linked_list.insert(data)
print("Reversed linked list: ", end="")
linked_list.reverse_linked_list()
You can also try this code with Online Python Compiler
Run Code

Java

import java.util.Scanner;
import java.util.Stack;

class Node {
int data;
Node next;

Node(int data) {
this.data = data;
this.next = null;
}
}

class LinkedList {
Node head;

public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}

public void reverseLinkedList() {
Stack<Node> nodeStack = new Stack<>();
Node current = head;
while (current.next != null) {
nodeStack.push(current);
current = current.next;
}
head = current;
Node previousTop = current;
while (!nodeStack.isEmpty()) {
current = nodeStack.pop();
previousTop.next = current;
previousTop = current;
}
previousTop.next = null;
printLinkedList();
}

public void printLinkedList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
LinkedList list = new LinkedList();

System.out.print("Enter the number of nodes: ");
int totalNodes = sc.nextInt();

System.out.println("Enter node data:");
for (int i = 0; i < totalNodes; i++) {
int data = sc.nextInt();
list.insert(data);
}

System.out.print("Reversed linked list: ");
list.reverseLinkedList();
sc.close();
}
}
You can also try this code with Online Java Compiler
Run Code

C#

using System;
using System.Collections.Generic;

class Node {
public int data;
public Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}

class LinkedList {
Node head;

public void Insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}

public void ReverseLinkedList() {
Stack<Node> stack = new Stack<Node>();
Node current = head;
while (current.next != null) {
stack.Push(current);
current = current.next;
}
head = current;
Node previousTop = current;
while (stack.Count > 0) {
current = stack.Pop();
previousTop.next = current;
previousTop = current;
}
previousTop.next = null;
PrintLinkedList();
}

public void PrintLinkedList() {
Node current = head;
while (current != null) {
Console.Write(current.data + " ");
current = current.next;
}
Console.WriteLine();
}

static void Main() {
Console.Write("Enter the number of nodes: ");
int totalNodes = int.Parse(Console.ReadLine());
LinkedList linkedList = new LinkedList();

Console.WriteLine("Enter node data:");
for (int i = 0; i < totalNodes; i++) {
int data = int.Parse(Console.ReadLine());
linkedList.Insert(data);
}

Console.Write("Reversed linked list: ");
linkedList.ReverseLinkedList();
}
}

JavaScript

class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}

class LinkedList {
constructor() {
this.head = null;
}

insert(data) {
let newNode = new Node(data);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}

reverseLinkedList() {
let stack = [];
let current = this.head;
while (current.next) {
stack.push(current);
current = current.next;
}
this.head = current;
let previousTop = current;
while (stack.length > 0) {
current = stack.pop();
previousTop.next = current;
previousTop = current;
}
previousTop.next = null;
this.printLinkedList();
}

printLinkedList() {
let current = this.head;
let result = [];
while (current) {
result.push(current.data);
current = current.next;
}
console.log(result.join(" "));
}
}

// Driver code
const linkedList = new LinkedList();
const totalNodes = parseInt(prompt("Enter the number of nodes: "));
for (let i = 0; i < totalNodes; i++) {
const data = parseInt(prompt("Enter node data:"));
linkedList.insert(data);
}
console.log("Reversed linked list:");
linkedList.reverseLinkedList();
You can also try this code with Online Javascript Compiler
Run Code

 

Input

Enter the number of nodes in the linked list: 6
Enter the data of nodes: 1 2 3 6 5 4

Output

Reversed linked list: 4 5 6 3 2 1

Complexity Analysis

Time Complexity: Traversal through the linked list is required to store the nodes of the linked list in the stack. Similarly, the linked list nodes are popped off the stack one by one until the stack is empty. Both these operations are linear-time operations. So, the time complexity of this method is O(N), where ‘N’ represents the number of nodes in the linked list.

Space Complexity: Additional space is required to store the nodes of the linked list in the stack. The space required is linearly proportional to the size of the linked list. So, the space complexity of this method is O(N), where ‘N’ represents the number of nodes in the linked list.

 

Approach 2: Using Iteration with constant space

In the previous method, we first traversed through the linked list to store all the nodes. If you notice, we only need two nodes at a time for reversal: ‘PREVIOUS_TOP’ and ‘CURRENT’ to reverse the pointer of one node at a time.

illustration image

Rather than start reversing the linked list from end, we can start the reversal from the Rather than start reversing the linked list from the end, we can start the reversal from the beginning.

illustration image

The problem we’ll face here is that if we redirect the ‘NEXT’ pointer of ‘NODE_2’, the linked list is split into two parts. This makes moving to the ‘NEXT’ node impossible. Refer to the figure given below for the illustration of the same.

illustration image

The solution for this problem is to add a pointer ‘NEXT_TO_CURRENT’ pointer to store the address of the pointer ‘NEXT’ to current.

illustration image

After setting the pointer of the ‘NEXT’ node, we can make the ‘PREVIOUS_TOP’ node our ‘CURRENT ’node and move the ‘CURRENT’ node to the next node. 

illustration image

These actions are repeated until the linked list is completely traversed. In the end, the ‘PREVIOUS_TOP’ points to the last node of the linked list. As the last node of a linked list becomes the first node when the linked list is reversed, we consider ‘PREVIOUS_TOP’ to be the ‘HEAD’ of the newly created linked list. Refer to the algorithm given below for a better understanding.

Algorithm

  • Set the ‘CURRENT’ equal to ‘HEAD’.
  • Set the ‘PREVIOUS_TOP’ equal to NULL(First element of the linked list should point to NULL after reversal).
  • Declare ‘NEXT_TO_CURRENT’ node pointer.
  • While ‘CURRENT’ is not equal to NULL, do:
    • Set NEXT_TO_CURRENT  = CURRENT -> NEXT.
    • Set CURRENT -> NEXT = PREVIOUS_TOP.
    • Set PREVIOUS_TOP = CURRENT.
    • Set CURRENT = NEXT.
  • Set HEAD = PREVIOUS_TOP.

Implementation

  • C++
  • C
  • Java
  • Python
  • JavaScript
  • C#

C++

#include <iostream>
using namespace std;

// 'NODE' class to store linked list nodes.
class Node
{

public:
int data;
Node *next;

// Constructor to create a node with given data.
Node(int data)
{
this->data = data;
next = NULL;
}
};

// 'LINKED_LIST' class to create linked list objects.
class LinkedList
{

// 'HEAD' node to store the address of the first node.
Node *head;

public:
LinkedList()
{
head = NULL;
}

// Function to print the linked list elements.
void printLinkedList()
{

/* 'CURRENT' node pointer traverses through the linked list.
Set 'CURRENT' node equal to first node of the linked list.
*/
Node *current = head;

// Loop to traverse the linked list.
while (current)
{
cout << current->data << " ";
current = current->next;
}
cout << endl;
}

// Function to insert nodes in the linked list.
void insert(int data)
{

/* If linked list is empty, create a new node
and direct the 'HEAD' node to the newly created node.
*/
if (head == NULL)
{
head = new Node(data);
return;
}

// Else traverse the linked list until end of the list is encountered.
Node *current = head;
while (current->next)
{
current = current->next;
}

// Create and insert a new node at the end of the linked list.
current->next = new Node(data);
}

void reverseLinkedList()
{

// Set 'CURRENT' node equal to the first node of the linked list.
Node *current = head;

// Initialise 'PREVIOUS_TOP' as NULL to store the previous top element.
Node *previousTop = NULL;

// Traverse through the linked list and redirecting the pointers to the previous elements.
while (current)
{

// Initialise 'NEXT_TO_CURRENT' node pointer with CURRENT -> NEXT.
Node *nextToCurrent = current->next;

// Redirect 'NEXT' pointer of the 'CURRENT' node.
current->next = previousTop;

// Move pointers to the next node of linked list.
previousTop = current;
current = nextToCurrent;
}

// Point 'HEAD' equal to the last node of the linked list.
head = previousTop;

// Print the reversed linked list.
printLinkedList();
}
};

int main()
{
int totalNodes;
cout << "Enter the number of nodes in the linked list: ";
cin >> totalNodes;

cout << "Enter the data of nodes: ";
LinkedList *givenList = new LinkedList();
for (int i = 0; i < totalNodes; i++)
{
int data;
cin >> data;
givenList->insert(data);
}
cout << "Reversed linked list: ";
givenList->reverseLinkedList();
}
You can also try this code with Online C++ Compiler
Run Code

C

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct Node* head = NULL;

void insert(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;

if (head == NULL) {
head = newNode;
} else {
struct Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}

void reverseLinkedList() {
struct Node* previousTop = NULL;
struct Node* current = head;
struct Node* nextToCurrent = NULL;

while (current != NULL) {
nextToCurrent = current->next;
current->next = previousTop;
previousTop = current;
current = nextToCurrent;
}
head = previousTop;
}

void printLinkedList() {
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

int main() {
int totalNodes, data;
printf("Enter the number of nodes in the linked list: ");
scanf("%d", &totalNodes);

printf("Enter the data of nodes: ");
for (int i = 0; i < totalNodes; i++) {
scanf("%d", &data);
insert(data);
}

printf("Reversed linked list: ");
reverseLinkedList();
printLinkedList();

return 0;
}
You can also try this code with Online C Compiler
Run Code

Java

import java.util.Scanner;

class Node {
int data;
Node next;

Node(int data) {
this.data = data;
this.next = null;
}
}

class LinkedList {
Node head;

public void insert(int data) {
if (head == null) {
head = new Node(data);
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = new Node(data);
}
}

public void reverseLinkedList() {
Node current = head;
Node previousTop = null;

while (current != null) {
Node nextToCurrent = current.next;
current.next = previousTop;
previousTop = current;
current = nextToCurrent;
}
head = previousTop;
}

public void printLinkedList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
LinkedList linkedList = new LinkedList();

System.out.print("Enter the number of nodes in the linked list: ");
int totalNodes = scanner.nextInt();

System.out.println("Enter the data of nodes: ");
for (int i = 0; i < totalNodes; i++) {
int data = scanner.nextInt();
linkedList.insert(data);
}

System.out.println("Reversed linked list: ");
linkedList.reverseLinkedList();
linkedList.printLinkedList();
}
}
You can also try this code with Online Java Compiler
Run Code

Python

class Node:
def __init__(self, data):
self.data = data
self.next = None

class LinkedList:
def __init__(self):
self.head = None

def insert(self, data):
if not self.head:
self.head = Node(data)
else:
current = self.head
while current.next:
current = current.next
current.next = Node(data)

def reverse_linked_list(self):
current = self.head
previous_top = None

while current:
next_to_current = current.next
current.next = previous_top
previous_top = current
current = next_to_current

self.head = previous_top

def print_linked_list(self):
current = self.head
while current:
print(current.data, end=" ")
print()

if __name__ == "__main__":
linked_list = LinkedList()
total_nodes = int(input("Enter the number of nodes in the linked list: "))

print("Enter the data of nodes: ")
for _ in range(total_nodes):
data = int(input())
linked_list.insert(data)

print("Reversed linked list: ")
linked_list.reverse_linked_list()
linked_list.print_linked_list()
You can also try this code with Online Python Compiler
Run Code

JavaScript

class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}

class LinkedList {
constructor() {
this.head = null;
}

insert(data) {
const newNode = new Node(data);
if (this.head === null) {
this.head = newNode;
} else {
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = newNode;
}
}

reverseLinkedList() {
let current = this.head;
let previousTop = null;

while (current !== null) {
let nextToCurrent = current.next;
current.next = previousTop;
previousTop = current;
current = nextToCurrent;
}
this.head = previousTop;
}

printLinkedList() {
let current = this.head;
const result = [];
while (current !== null) {
result.push(current.data);
current = current.next;
}
console.log(result.join(" "));
}
}

const linkedList = new LinkedList();
const totalNodes = parseInt(prompt("Enter the number of nodes in the linked list:"));
console.log("Enter the data of nodes: ");
for (let i = 0; i < totalNodes; i++) {
const data = parseInt(prompt("Enter node data:"));
linkedList.insert(data);
}

console.log("Reversed linked list:");
linkedList.reverseLinkedList();
linkedList.printLinkedList();
You can also try this code with Online Javascript Compiler
Run Code

C#

using System;

class Node {
public int data;
public Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}

class LinkedList {
private Node head;

public void Insert(int data) {
if (head == null) {
head = new Node(data);
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = new Node(data);
}
}

public void ReverseLinkedList() {
Node current = head;
Node previousTop = null;

while (current != null) {
Node nextToCurrent = current.next;
current.next = previousTop;
previousTop = current;
current = nextToCurrent;
}

head = previousTop;
}

public void PrintLinkedList() {
Node current = head;
while (current != null) {
Console.Write(current.data + " ");
current = current.next;
}
Console.WriteLine();
}
}

class Program {
static void Main(string[] args) {
LinkedList linkedList = new LinkedList();

Console.Write("Enter the number of nodes in the linked list: ");
int totalNodes = int.Parse(Console.ReadLine());

Console.WriteLine("Enter the data of nodes: ");
for (int i = 0; i < totalNodes; i++) {
int data = int.Parse(Console.ReadLine());
linkedList.Insert(data);
}

Console.WriteLine("Reversed linked list: ");
linkedList.ReverseLinkedList();
linkedList.PrintLinkedList();
}
}


Input

Enter the number of nodes in the linked list: 5
Enter the data of nodes: 10 32 20 11 2

Output

Reversed linked list: 2 11 20 32 10

Complexity Analysis

Time Complexity: Traversal through the linked list is required to reverse the pointers of the linked list nodes. Traversal through the linked list is a linear-time operation. So, the time complexity of this method is O(N), where ‘N’ represents the number of nodes in the linked list.

Space Complexity: Constant space is required to store the ‘PREVIOUS_TOP’, ‘CURRENT’, and ‘NEXT_TO_CURRENT’ pointers. So, the space complexity of the method is O(1).

Must Read  C Program to Reverse a Number

Method 3: Recursion with constant space

The operations discussed above can also be achieved using recursion. The ‘PREVIOUS_TOP’, ‘CURRENT’, and ‘HEAD’ pointers are fed to the recursive functions as the function parameters.

The base function of the recursive function is to check whether the ‘NEXT’ pointer to the ‘CURRENT’ node exists. If no ‘NEXT’ pointer exists, that means we have encountered the last node of the list. So, the last node of the linked list should be stored as the head of the reversed linked list.

Like the iterative solution, we set the ‘NEXT’ node of the ‘CURRENT’ node into a variable ‘NEXT_TO_CURRENT’. The ‘NEXT’ pointer of the ‘CURRENT’ node is redirected to the ‘PREVIOUS_TOP’. After redirection, ’PREVIOUS_TOP’ is set to ‘CURRENT’, and the ‘CURRENT’ is set to ‘NEXT_TO_CURRENT’. The recursive function will be called using the new parameters. Refer to the given algorithm for a better understanding.

Algorithm

  • If CURRENT -> NEXT is equal to NULL, then:
    • Set ‘HEAD’ = ‘CURRENT’.
    • Set CURRENT -> NEXT = PREVIOUS_TOP.
    • Return
  • Set NEXT_TO_CURRENT = CURRENT -> NEXT.
  • Set CURRENT -> NEXT = PREVIOUS_TOP.
  • Call the recursive function with ‘NEXT_TO_CURRENT’ and ‘CURRENT parameters.

Implementation

  • C++
  • C
  • Java
  • Python
  • C#
  • JavaScript

C++

#include <iostream>
using namespace std;

// 'NODE' class to store linked list nodes.
class Node
{

public:
int data;
Node *next;

// Constructor to create a node with given data.
Node(int data)
{
this->data = data;
next = NULL;
}
};

// 'LINKED_LIST' class to create linked list objects.
class LinkedList
{

// 'HEAD' node to store the address of the first node.
Node *head;

public:
LinkedList()
{
head = NULL;
}

// Function to print the linked list elements.
void printLinkedList()
{

/* 'CURRENT' node pointer traverses through the linked list.
Set 'CURRENT' node equal to first node of the linked list.
*/
Node *current = head;

// Loop to traverse the linked list.
while (current)
{
cout << current->data << " ";
current = current->next;
}
cout << endl;
}

// Function to insert nodes in the linked list.
void insert(int data)
{

/* If linked list is empty, create a new node
and direct the 'HEAD' node to the newly created node.
*/
if (head == NULL)
{
head = new Node(data);
return;
}

// Else traverse the linked list until end of the list is encountered.
Node *current = head;
while (current->next)
{
current = current->next;
}

// Create and insert a new node at the end of the linked list.
current->next = new Node(data);
}

void reverseLinkedListHelper(Node *current, Node *previousTop)
{

/* Last node of the linked list.
Point 'HEAD' to this node.
*/
if (!current->next)
{
head = current;
current->next = previousTop;
return;
}

// Initialize 'NEXT_TO_CURRENT' pointer with CURRENT->NEXT.
Node *nextToCurrent = current->next;

// Redirect 'NEXT' pointer of the 'CURRENT' node.
current->next = previousTop;

// Call the recursive function with 'NEXT_TO_CURRENT' and 'CURRENT' parameters.
reverseLinkedListHelper(nextToCurrent, current);
}

void reverseLinkedList()
{

// If 'HEAD' is not pointing to any node, list is empty.
if (!head)
return;

// Set 'CURRENT' node equal to first node of the linked list.
Node *current = head;

/* Set 'PREVIOUS_TOP' node to NULL to represent
end of the linked list after reversal.
*/
Node *previousTop = NULL;

// Call helper function to reverse the linked list.
reverseLinkedListHelper(current, previousTop);

// Print the reversed linked list.
printLinkedList();
}
};

int main()
{
int totalNodes;
cout << "Enter the number of nodes in the linked list: ";
cin >> totalNodes;

cout << "Enter the data of nodes: ";
LinkedList *givenList = new LinkedList();
for (int i = 0; i < totalNodes; i++)
{
int data;
cin >> data;
givenList->insert(data);
}
cout << "Reversed linked list: ";
givenList->reverseLinkedList();
}
You can also try this code with Online C++ Compiler
Run Code

C

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

void insert(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = *head;
*head = newNode;
}

void printLinkedList(struct Node* head) {
while (head) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}

struct Node* reverseLinkedList(struct Node* head) {
struct Node* prev = NULL;
struct Node* current = head;
struct Node* next = NULL;

while (current) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}

int main() {
struct Node* head = NULL;
int totalNodes, data;

printf("Enter the number of nodes in the linked list: ");
scanf("%d", &totalNodes);

printf("Enter the data of nodes: ");
for (int i = 0; i < totalNodes; i++) {
scanf("%d", &data);
insert(&head, data);
}

printf("Reversed linked list: ");
head = reverseLinkedList(head);
printLinkedList(head);
}
You can also try this code with Online C Compiler
Run Code

Java

class Node {
int data;
Node next;

Node(int data) {
this.data = data;
this.next = null;
}
}

class LinkedList {
Node head;

public void insert(int data) {
if (head == null) {
head = new Node(data);
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = new Node(data);
}

public void printLinkedList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}

public Node reverseLinkedList(Node node) {
Node prev = null;
Node current = node;
Node next;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
return head;
}

public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
System.out.println("Original List:");
list.printLinkedList();
System.out.println("Reversed List:");
list.reverseLinkedList(list.head);
list.printLinkedList();
}
}
You can also try this code with Online Java Compiler
Run Code

Python

class Node:
def __init__(self, data):
self.data = data
self.next = None

class LinkedList:
def __init__(self):
self.head = None

def insert(self, data):
if self.head is None:
self.head = Node(data)
return
current = self.head
while current.next:
current = current.next
current.next = Node(data)

def print_linked_list(self):
current = self.head
while current:
print(current.data, end=" ")
current = current.next
print()

def reverse_linked_list(self):
prev = None
current = self.head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
self.head = prev

# Example usage:
ll = LinkedList()
ll.insert(1)
ll.insert(2)
ll.insert(3)
print("Original List:")
ll.print_linked_list()
ll.reverse_linked_list()
print("Reversed List:")
ll.print_linked_list()
You can also try this code with Online Python Compiler
Run Code

C#

using System;

class Node {
public int data;
public Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}

class LinkedList {
private Node head;

public void Insert(int data) {
if (head == null) {
head = new Node(data);
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = new Node(data);
}

public void PrintLinkedList() {
Node current = head;
while (current != null) {
Console.Write(current.data + " ");
current = current.next;
}
Console.WriteLine();
}

public void ReverseLinkedList() {
Node prev = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
}

class Program {
static void Main() {
LinkedList list = new LinkedList();
list.Insert(1);
list.Insert(2);
list.Insert(3);
Console.WriteLine("Original List:");
list.PrintLinkedList();
list.ReverseLinkedList();
Console.WriteLine("Reversed List:");
list.PrintLinkedList();
}
}

JavaScript

class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}

class LinkedList {
constructor() {
this.head = null;
}

insert(data) {
if (this.head === null) {
this.head = new Node(data);
return;
}
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = new Node(data);
}

printLinkedList() {
let current = this.head;
let result = "";
while (current) {
result += current.data + " ";
current = current.next;
}
console.log(result.trim());
}

reverseLinkedList() {
let prev = null;
let current = this.head;
let next = null;
while (current) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
this.head = prev;
}
}

// Example usage:
let list = new LinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
console.log("Original List:");
list.printLinkedList();
list.reverseLinkedList();
console.log("Reversed List:");
list.printLinkedList();
You can also try this code with Online Javascript Compiler
Run Code

Input

Enter the number of nodes in the linked list: 4
Enter the data of nodes: 1 2 3 4

Output

Reversed linked list: 4 3 2 1

Complexity Analysis

Time Complexity: Traversal through the linked list is required to reverse the pointers of the linked list nodes. Traversal through the linked list is a linear-time operation. So, the time complexity of this method is O(N), where ‘N’ represents the number of nodes in the linked list.

Space Complexity: The recursion stack space requires O(N) space.

Skimming through blogs can be perplexing at times, so let's watch a video to quickly learn how to reverse a Linked List - Iteratively & Recursively.

Frequently Asked Question

What are the main steps involved in reversing a singly linked list?

To reverse a singly linked list, initialize three pointers: prev, current, and next. Traverse the list, setting each node’s next pointer to prev, updating prev and current sequentially until the list is fully reversed.

How many pointers are required to reverse a linked list?

Reversing a singly linked list typically requires three pointers: prev, current, and next. The prev pointer tracks the reversed part, current points to the node being processed, and next temporarily holds the next node in the original sequence.

How can reversing a linked list affect its usability or performance in an application?

Reversing a linked list can improve access to the last node but may slow down applications requiring the original order. It also changes node traversal direction, potentially impacting algorithms that depend on sequential data access.

Why do we need to reverse a linked list?

The node’s next property determines the order in a singly linked list. This could either refer to another node or point to null if it is the last node in the list. Reversing a linked list, therefore, refers to reassigning all the next properties on every node.

Conclusion

Reversing a linked list may look like a simple operation. However, the applications of linked list reversal are vast. Many algorithms related to linked lists are based on the linked list reversal.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Code360

Live masterclass