Data Structures & Algorithms
Table of content:
- What Is Data Structure?
- Key Features Of Data Structures
- Basic Terminologies Related To Data Structures
- Types Of Data Structures
- What Are Linear Data Structures & Its Types?
- What Are Non-Linear Data Structures & Its Types?
- Importance Of Data Structure In Programming
- Basic Operations On Data Structures
- Applications Of Data Structures
- Real-Life Applications Of Data Structures
- Linear Vs. Non-linear Data Structures
- What Are Algorithms? The Difference Between Data Structures & Algorithms
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Asymptotic Notation?
- How Asymptotic Notation Helps In Analyzing Performance
- Types Of Asymptotic Notation
- Big-O Notation (O)
- Omega Notation (Ω)
- Theta Notation (Θ)
- Little-O Notation (o)
- Little-Omega Notation (ω)
- Summary Of Asymptotic Notations
- Real-World Applications Of Asymptotic Notation
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding Big O Notation
- Types Of Time Complexity
- Space Complexity In Big O Notation
- How To Determine Big O Complexity
- Best, Worst, And Average Case Complexity
- Applications Of Big O Notation
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Time Complexity?
- Why Do You Need To Calculate Time Complexity?
- The Time Complexity Algorithm Cases
- Time Complexity: Different Types Of Asymptotic Notations
- How To Calculate Time Complexity?
- Time Complexity Of Sorting Algorithms
- Time Complexity Of Searching Algorithms
- Writing And optimizing An algorithm
- What Is Space Complexity And Its Significance?
- Relation Between Time And Space Complexity
- Conclusion
Table of content:
- What Is Linear Data Structure?
- Key Characteristics Of Linear Data Structures
- What Are The Types Of Linear Data Structures?
- What Is An Array Linear Data Structure?
- What Are Linked Lists Linear Data Structure?
- What Is A Stack Linear Data Structure?
- What Is A Queue Linear Data Structure?
- Most Common Operations Performed in Linear Data Structures
- Advantages Of Linear Data Structures
- What Is Nonlinear Data Structure?
- Difference Between Linear & Non-Linear Data Structures
- Who Uses Linear Data Structures?
- Conclusion
- Frequently Asked Questions
Table of content:
- What is a linear data structure?
- What is a non-linear data structure?
- Difference between linear data structure and non-linear data structure
- FAQs about linear and non-linear data structures
Table of content:
- What Is Sorting In Data Structures?
- What Is Bubble Sort?
- What Is Selection Sort?
- What Is Insertion Sort?
- What Is Merge Sort?
- What Is Quick Sort?
- What Is Heap Sort?
- What Is Radix Sort?
- What Is Bucket Sort?
- What Is Counting Sort?
- What Is Shell Sort?
- Choosing The Right Sorting Algorithm
- Applications Of Sorting
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding Bubble Sort Algorithm
- Bubble Sort Algorithm
- Implementation Of Bubble Sort In C++
- Time And Space Complexity Analysis Of Bubble Sort Algorithm
- Advantages Of Bubble Sort Algorithm
- Disadvantages Of Bubble Sort Algorithm
- Applications of Bubble Sort Algorithms
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding The Merge Sort Algorithm
- Algorithm For Merge Sort
- Implementation Of Merge Sort In C++
- Time And Space Complexity Analysis Of Merge Sort
- Advantages And Disadvantages Of Merge Sort
- Applications Of Merge Sort
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding The Selection Sort Algorithm
- Algorithmic Approach To Selection Sort
- Implementation Of Selection Sort Algorithm
- Complexity Analysis Of Selection Sort
- Comparison Of Selection Sort With Other Sorting Algorithms
- Advantages And Disadvantages Of Selection Sort
- Application Of Selection Sort
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Insertion Sort Algorithm?
- How Does Insertion Sort Work? (Step-by-Step Explanation)
- Implementation of Insertion Sort in C++
- Time And Space Complexity Of Insertion Sort
- Applications Of Insertion Sort Algorithm
- Comparison With Other Sorting Algorithms
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding Quick Sort Algorithm
- Step-By-Step Working Of Quick Sort
- Implementation Of Quick Sort Algorithm
- Time Complexity Analysis Of Quick Sort
- Advantages Of Quick Sort Algorithm
- Disadvantages Of Quick Sort Algorithm
- Applications Of Quick Sort Algorithm
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding The Heap Data Structure
- Working Of Heap Sort Algorithm
- Implementation Of Heap Sort Algorithm
- Advantages Of Heap Sort
- Disadvantages Of Heap Sort
- Real-World Applications Of Heap Sort
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding The Counting Sort Algorithm
- Conditions For Using Counting Sort Algorithm
- How Counting Sort Algorithm Works?
- Implementation Of Counting Sort Algorithm
- Time And Space Complexity Analysis Of Counting Sort
- Comparison Of Counting Sort With Other Sorting Algorithms
- Advantages Of Counting Sort Algorithm
- Disadvantages Of Counting Sort Algorithm
- Applications Of Counting Sort Algorithm
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding Shell Sort Algorithm
- Working Of Shell Sort Algorithm
- Implementation Of Shell Sort Algorithm
- Time Complexity Analysis Of Shell Sort Algorithm
- Advantages Of Shell Sort Algorithm
- Disadvantages Of Shell Sort Algorithm
- Applications Of Shell Sort Algorithm
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is The Binary Search Algorithm?
- Conditions For Using Binary Search
- Steps For Implementing Binary Search
- Iterative Method For Binary Search With Implementation Examples
- Recursive Method For Binary Search
- Complexity Analysis Of Binary Search Algorithm
- Iterative Vs. Recursive Implementation Of Binary Search
- Advantages & Disadvantages Of Binary Search
- Practical Applications & Real-World Examples Of Binary Search
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Linked List In Data Structures?
- Types Of Linked Lists In Data Structures
- Linked List Operations In Data Structures
- Advantages And Disadvantages Of Linked Lists In Data Structures
- Comparison Of Linked Lists And Arrays
- Applications Of Linked Lists
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is A Singly Linked List In Data Structure?
- Insertion Operations On Singly Linked Lists
- Deletion Operation On Singly Linked List
- Searching For Elements In Single Linked List
- Calculating Length Of Single Linked List
- Practical Applications Of Singly Linked Lists In Data Structure
- Common Problems With Singly Linked Lists
- Conclusion
- Frequently Asked Questions (FAQ)
Table of content:
- What Is A Linked List?
- Reverse A Linked List
- How To Reverse A Linked List? (Approaches)
- Recursive Approach To Reverse A Linked List
- Iterative Approach To Reverse A Linked List
- Using Stack To Reverse A Linked List
- Complexity Analysis Of Different Approaches To Reverse A Linked List
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is A Graph Data Structure?
- Importance Of Graph Data Structures
- Types Of Graphs In Data Structure
- Types Of Graph Algorithms
- Application Of Graphs In Data Structures
- Challenges And Complexities In Graphs
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Tree Data Structure?
- Terminologies Of Tree Data Structure:
- Different Types Of Tree Data Structures
- Basic Operations On Tree Data Structure
- Applications Of Tree Data Structures
- Comparison Of Trees, Graphs, And Linear Data Structures
- Advantages Of Tree Data Structure
- Disadvantages Of Tree Data Structure
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Dynamic Programming?
- Real-Life Example: The Jigsaw Puzzle Analogy
- How To Solve A Problem Using Dynamic Programming?
- Dynamic Programming Algorithm Techniques
- Advantages Of Dynamic Programming
- Disadvantages Of Dynamic Programming
- Applications Of Dynamic Programming
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding The Sliding Window Algorithm
- How Does The Sliding Window Algorithm Works?
- How To Identify Sliding Window Problems?
- Fixed-Size Sliding Window Example: Maximum Sum Subarray Of Size k
- Variable-Size Sliding Window Example: Smallest Subarray With A Given Sum
- Advantages Of Sliding Window Technique
- Disadvantages Of Sliding Window Technique
- Conclusion
- Frequently Asked Questions
Table of content:
- Introduction To Data Structures
- Data Structures Interview Questions: Basics
- Data Structures Interview Questions: Intermediate
- Data Structures Interview Questions: Advanced
- Conclusion
Reverse A Linked List | All Approaches Explained +Code Examples

Ever tried flipping a stack of pancakes without making a mess? Reversing a linked list is kind of like that–except without the risk of syrup stains.
In this blog, we’ll explore how to reverse a linked list using three different approaches: recursive, iterative, and stack-based. Whether you’re prepping for coding interviews or just strengthening your DSA fundamentals, this article will give you a clear and structured understanding of the problem and its solutions.
What Is A Linked List?
A linked list is a linear data structure where elements (nodes) are connected using pointers. Each node consists of:
- Data (stores the value)
- Pointer/Reference (stores the address of the next node)
Unlike arrays, linked lists don’t require contiguous memory allocation, making them more flexible for dynamic memory management. However, they also come with drawbacks, such as additional memory overhead for pointers and slower element access. Now that we know what a linked list is let’s discuss– how to reverse a linked list!
Reverse A Linked List
Reversing a linked list means changing the direction of pointers so that the last node becomes the head and the head becomes the last node.
Why Reverse A Linked List?
- Undo operations– Think of reversing an action history (e.g., backtracking in an editor).
- Navigating backward– Useful in scenarios like browser history management or playlist navigation.
- Algorithmic needs– Many problems, such as palindrome checking in linked lists, require reversal.
The Reversal Concept | Linked List
In a singly linked list, each node points to the next one. To reverse it, we need to redirect the pointers so that each node points to the previous one instead.
Here’s an example of a singly linked list before and after reversal:
How To Reverse A Linked List? (Approaches)
We can reverse a linked list data structure using three main approaches:
- Recursive Approach – Uses function calls to process nodes in reverse order.
- Iterative Approach – Modifies the pointers step by step using a loop.
- Stack-Based Approach – Uses an auxiliary stack to store nodes and rearrange them.
In the following sections, we’ll explore the above-mentioned methods in detail with implementation examples.
Recursive Approach To Reverse A Linked List
Recursion is like a chain of stacked dominos–each function call depends on the previous one. In the recursive approach to reversing a linked list, we keep diving deeper into the list until we reach the last node, then start re-linking nodes in reverse order as we return from each recursive call.
How It Works (Step-by-Step)
- Base Case: If the linked list is empty or has only one node, return the head as it’s already reversed.
- Recursive Step: Recursively reverse the rest of the list, starting from the second node.
- Reverse Pointers: Update the next node’s pointer to point back to the current node.
- Fix the Last Node: Ensure the original head’s next pointer is set to NULL to mark the new end.
Visual Representation Of Recursive Approach To Reverse A Linked List
Before Recursion:
head → [10 | *] → [20 | *] → [30 | *] → NULL
During Recursion (Breaking Down)
The function keeps calling itself until it reaches the base case:
Reverse([10 | *] → [20 | *] → [30 | *] → NULL)
↳ Reverse([20 | *] → [30 | *] → NULL)
↳ Reverse([30 | *] → NULL) → Base case reached
At this point, [30] is the last node and will become the new head.
Rewiring Pointers (Returning From Recursion)
Now, we start linking nodes in reverse order:
[30 | *] ← [20 | *] ← [10 | NULL]
New Head → [30 | *]
- 20->next->next = 20 makes [30] point to [20].
- 20->next = NULL disconnects [20] from [30].
- 10->next->next = 10 makes [20] point to [10].
- 10->next = NULL disconnects [10] from [20].
Final Reversed Linked List:
New Head → [30 | *] → [20 | *] → [10 | NULL]
Code Implementation For Recursive Approach To Reverse A Linked List
In this section, we will look at the code implementation of this approach to reverse a linked list.
Recursive Approach To Reverse A Linked List C++ Example
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(NULL) {}
};
Node* reverseRecursive(Node* head) {
if (!head || !head->next) return head;
Node* newHead = reverseRecursive(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
// Function to print linked list
void printList(Node* head) {
while (head) {
cout << head->data << " -> ";
head = head->next;
}
cout << "NULL" << endl;
}
// Driver code
int main() {
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
cout << "Original List: ";
printList(head);
head = reverseRecursive(head);
cout << "Reversed List: ";
printList(head);
return 0;
}
Output:
Original List: 10 -> 20 -> 30 -> NULL
Reversed List: 30 -> 20 -> 10 -> NULL
Code Explanation:
In the example above, we first include the header file <iostream> for input/output operations and use the std namespace to use standard library functions directly.
- Structure For Linked List: We define a structure Node containing data (and integer data type variable member to store the node's value), next (a pointer variable that points to the next node), and constructor Node(int val) to initialize the node with a given value and set next to NULL.
- Recursive Function: Then, we define the C++ function reverseRecursive(Node* head). Inside the function, we define the base case and recursive call as follows:
- Base Case: We use an if-statement to check if the head node is NULL.
- If head == NULL (empty list) or head->next == NULL (only one node exists), return head as the list is already reversed.
- Recursive Call: The function recursively moves to the last node by calling reverseRecursive(head->next).
- Once it reaches the last node, the recursion starts unwinding, and nodes begin re-linking in reverse order.
- Rewiring the Pointers: After every recursive call, we modify the next pointer of the next node to point back to the current node:
- head->next->next = head;– This makes the next node’s next pointer (which was previously NULL) point back to head.
- We then set head->next = NULL; to ensure that the old head (which becomes the last node in the reversed list) no longer points to the next node.
- Returning the New Head: The function returns newHead, which is the last node of the original list but becomes the new head of the reversed list.
- Main Execution: We create a linked list in the main() function by first initializing the head node using new Node(10).
- Then we add subsequent nodes by setting head->next = new Node(20); and head->next->next = new Node(30);.
- Next, we print the original linked list using the printList(head) function, which traverses the list and prints its elements in order.
- We then call the function reverseRecursive(head), which reverses the linked list recursively and updates head with the new head of the reversed list.
- Finally, we print the reversed list using printList(head) again to display the modified order of elements.
This ensures that the linked list is reversed in place with a time complexity of O(n) and space complexity of O(n) due to the recursive call stack.
Recursive Approach To Reverse A Linked List Python Example
class Node:
def __init__(self, data):
self.data = data
self.next = None
def reverse_recursive(head):
if not head or not head.next:
return head
new_head = reverse_recursive(head.next)
head.next.next = head
head.next = None
return new_head
def print_list(head):
while head:
print(head.data, end=" -> ")
head = head.next
print("NULL")
# Driver code
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
print("Original List:", end=" ")
print_list(head)
head = reverse_recursive(head)
print("Reversed List:", end=" ")
print_list(head)
Code Explanation:
In the Python program example, we define a class to create the linked list, a recursive function to reverse it, and a print function (print_list()) to display the linked lists.
- Class Definition: We define a Node class with attributes data (to store the value) and next (to point to the next node). This will be used to create the Python linked list.
- Recursive Function (reverse_recursive): We define a Python function to reverse the linked list. Inside, we have:
- Base Case: Using an if-statement, we check if the head node is None or only one node exists. In either situation, the function returns the head.
- Recursive Call: If the base is unmet, the function recursively moves to the last node using reverse_recursive(head.next).
- Rewiring Pointers: After each recursive call, the function makes the next node point back to head (head.next.next = head) and breaks the old link (head.next = None).
- Main Execution: We create a linked list containing three nodes, 10, 20, and 30, and link them.
- We then print a string message to the console, and then the linked list is printed without the newline (using the end parameter).
- After that, we reverse the linked list using reverse_recursive(head) and then print the reversed list.
Recursive Approach To Reverse A Linked List Java Example
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
public static Node reverseRecursive(Node head) {
if (head == null || head.next == null) return head;
Node newHead = reverseRecursive(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " -> ");
head = head.next;
}
System.out.println("NULL");
}
public static void main(String[] args) {
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
System.out.print("Original List: ");
printList(head);
head = reverseRecursive(head);
System.out.print("Reversed List: ");
printList(head);
}
}
Code Explanation:
In the Java code example:
- Class Definition: We define a Node class with attributes data (to store value) and next (to point to the next node). This will be used to create the linked list.
- Recursive Function (reverseRecursive): Then, we define a recursive function to reverse a linked list. Inside the function:
- Base Case: If the head is null or only one node exists, return the head.
- Recursive Call: Call reverseRecursive(head.next) to reach the last node.
- Rewiring Pointers: head.next.next = head; makes the next node point back to head, and head.next = null; removes the old link.
- Main Execution: We create a linked list, print it, call reverseRecursive(head) to reverse it, and then print the reversed list.
Iterative Approach To Reverse A Linked List
Think of reversing a linked list iteratively, like flipping a stack of playing cards one by one—each card (node) needs to be placed in a new order by adjusting its connections without losing track of the next one. Instead of relying on recursive calls, we systematically move through the list, reversing the links as we go.
How It Works (Step-by-Step)
- Initialize Pointers: Start with three pointers:
- prev (initially NULL) to keep track of the reversed portion.
- curr (starting at head) to process the current node.
- next to temporarily store the next node before breaking the link.
- Iterate Through the List: Move curr through the list while adjusting pointers:
- Store curr->next in next to avoid losing the rest of the list.
- Reverse the link: Make curr->next point to prev.
- Move prev and curr one step forward.
- Update the Head: Once curr becomes NULL, prev holds the new head of the reversed list.
Visual Representation Of Iterative Approach To Reverse A Linked List
Initial Linked List:
head → [10] → [20] → [30] → [40] → NULL
Step-by-Step Reversal Process:
Step 1 (Before First Iteration)
prev = NULL curr = [10] → [20] → [30] → [40] → NULL
next = NULL (next will store curr->next)
Step 2 (Processing Node 10)
Store the next node: next = curr->next (next = [20])
Reverse the link: curr->next = prev ([10] → NULL)
Move prev and curr forward: prev = [10] → NULL
curr = [20] → [30] → [40] → NULL
Step 3 (Processing Node 20)
Store next = curr->next (next = [30])
Reverse the link: curr->next = prev ([20] → [10] → NULL)
Move prev and curr forward: prev = [20] → [10] → NULL
curr = [30] → [40] → NULL
Step 4 (Processing Node 30)
Store next = curr->next (next = [40])
Reverse the link: curr->next = prev ([30] → [20] → [10] → NULL)
Move prev and curr forward: prev = [30] → [20] → [10] → NULL
curr = [40] → NULL
Step 5 (Processing Node 40 - Last Node)
Store next = curr->next (next = NULL)
Reverse the link: curr->next = prev ([40] → [30] → [20] → [10] → NULL)
Move prev and curr forward: prev = [40] → [30] → [20] → [10] → NULL
curr = NULL (Loop ends)
Final Reversed Linked List:
head → [40] → [30] → [20] → [10] → NULL
At this point, prev is the new head of the reversed linked list.
Code Implementation For Iterative Approach To Reverse A Linked List
In this section, we will look at the code implementation of this approach to reverse a linked list in three languages: C++, Python, and Java.
Iterative Approach To Reverse A Linked List C++ Example
#include <iostream>
using namespace std;
// Node structure definition
struct Node {
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
// Function to reverse the linked list iteratively
Node* reverseIterative(Node* head) {
Node* prev = NULL;
Node* curr = head;
Node* next = NULL;
while (curr != NULL) {
next = curr->next; // Store the next node
curr->next = prev; // Reverse the current node's pointer
prev = curr; // Move prev to current
curr = next; // Move curr to next node
}
return prev; // New head of the reversed list
}
// Function to print linked list
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
// Main function
int main() {
// Creating linked list: 10 -> 20 -> 30 -> NULL
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
cout << "Original Linked List: ";
printList(head);
// Reverse the linked list iteratively
head = reverseIterative(head);
cout << "Reversed Linked List: ";
printList(head);
return 0;
}
Output:
Original Linked List: 10 20 30
Reversed Linked List: 30 20 10
Code Explanation:
In the C++ code example, we include the essential header and use the namespace.
- Structure For Linked List: Then, we define a structure Node containing: data (an integer to store the node’s value), next (a pointer to the next node in the list), and a constructor Node(int val) initializes the node with a given value and sets next to NULL.
- Iterative Function (reverseIterative): We then define a function to reverse a linked list.
- The function takes head as input and reverses the linked list in place using three pointers:
- prev (initially NULL) to keep track of the reversed portion.
- curr (starting at head) to process the current node.
- next to temporarily store the next node before breaking the link.
- Pointer Reversal Process: We then use a while loop to reverse the points.
- Store curr->next in next (to avoid losing access to the next node).
- Reverse the link by setting curr->next = prev.
- Move prev and curr forward by one node.
- The loop continues until curr becomes NULL. At this point, prev holds the new head of the reversed list, which is returned.
- Main Execution: We create a linked list is created in main() by initializing the head node (10), followed by linking 20 and 30.
- Then, we print the original linked list using printList(head).
- Next, we call the function reverseIterative(head) to reverse the list, and the new head is assigned back to head.
- The reversed linked list is printed again to display the modified order of elements.
This approach efficiently reverses the linked list in O(n) time and O(1) space, as it modifies pointers directly without extra recursion stack space.
Iterative Approach To Reverse A Linked List Python Example
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to reverse the linked list iteratively
def reverse_iterative(head):
prev = None
curr = head
while curr:
next_node = curr.next # Store the next node
curr.next = prev # Reverse the pointer
prev = curr # Move prev to current
curr = next_node # Move curr to next node   Â
return prev # New head of the reversed list
# Function to print linked list
def print_list(head):
while head:
print(head.data, end=" ")
head = head.next
print()
# Main execution
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
print("Original Linked List:", end=" ")
print_list(head)
head = reverse_iterative(head)
print("Reversed Linked List:", end=" ")
print_list(head)
Code Explanation:
- Class Definition: We first define a class Node with the constructor __init__(), which initializes class members: data, and next (default None). We will use this to create the linked list.
- Function Definition: Then we define a function reverse_iterative() to reverse a linked list iteratively. Inside the function, we first initialize three pointers:
- prev (initially None) to track the previous node.
- curr (starting at head) to traverse the list.
- next_node (to temporarily store the next node).
- Reversal Logic: The function then uses a while loop to iterate through the list and update the pointers as follows:
- Store the next node using next_node = curr.next.
- Reverse the current node’s link with curr.next = prev.
- Move prev and curr forward (prev = curr, curr = next_node).
- The process continues until curr becomes None, meaning we have traversed and reversed all nodes.
- Finally, return prev as the new head of the reversed linked list.
- Main Execution: We create a linked list (10 → 20 → 30) and print it to the console.
- Then, we reverse this linked list using the reverse_iterative(head) and print it.
- Time Complexity: O(n) | Space Complexity: O(1).
Recursive Approach To Reverse A Linked List Java Example
class Node {
int data;
Node next;
Node(int val) {
data = val;
next = null;
}
}
public class Main {
// Function to reverse linked list iteratively
static Node reverseIterative(Node head) {
Node prev = null;
Node curr = head;
Node next = null;
while (curr != null) {
next = curr.next; // Store the next node
curr.next = prev; // Reverse the link
prev = curr; // Move prev to current
curr = next; // Move curr to next node
}
return prev; // New head of the reversed list
}
// Function to print linked list
static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
// Creating linked list: 10 -> 20 -> 30 -> NULL
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
System.out.print("Original Linked List: ");
printList(head);
// Reverse the linked list iteratively
head = reverseIterative(head);
System.out.print("Reversed Linked List: ");
printList(head);
}
}
Code Explanation:
- Class Definition: We define a class Node with three members: data (int variable to store the value), next (a pointer to store the reference to the next node), and a constructor Node(int val) to initialize the node with a value and set next = null.
- Function Definition (reverseIterative): Then we define a function that reverses a linked list iteratively using three pointers:
- prev (initially null) → Tracks the previous node.
- curr (initially head) → The current node being processed.
- next (stores the next node before breaking the link).
- Reversal Logic: Then, we use a while loop to traverse the nodes until curr becomes null (curr != null).
- In each iteration, the loop saves the next node using next = curr.next before modifying links.
- Reverse the Link: Point the current node (curr.next) to the previous node (prev), breaking its original forward connection. Move Pointers Forward:
- Set prev = curr (move prev to the current node).
- Set curr = next (move curr to the next node).
- The loop continues until curr becomes null, meaning all nodes are reversed.
- Finally, return prev, which now holds the new head of the reversed linked list.
- Main Execution: We first create a linked list with three nodes and link them (10 → 20 → 30).
- We then print the original list using printList(head).
- Next, we reverse the list calling reverseIterative(head), which finally updates head.
- Lastly, we print the reverse list to the console.
- Time Complexity: O(n) | Space Complexity: O(1)
Using Stack To Reverse A Linked List
A stack follows the Last In, First Out (LIFO) principle, making it a great tool for reversing a linked list. Instead of modifying pointers directly, we push all nodes onto a stack and then pop them in reverse order to reconstruct the list.
How It Works (Step-by-Step)
- Push All Nodes onto the Stack:
- Traverse the linked list and push each node onto the stack.
- This stores the nodes in reverse order due to LIFO behavior.
- Pop Nodes and Reconstruct the List:
- Pop nodes one by one and re-link them to form a new reversed list.
- Update the head to the first popped node.
- Adjust the next pointers correctly for all nodes.
- Ensure the last node's next is set to NULL.
Visual Representation Of Stack-based Approach To Reverse A Linked List
Initial Linked List:
Head → [10 | *] → [20 | *] → [30 | NULL]
Step 1: Push Nodes onto Stack
(Stack stores nodes in reverse order of traversal)
Top → [30]
[20]
[10]
Step 2: Pop Nodes and Reconstruct List
- Pop 30 → New head → Head → [30 | *]
- Pop 20 → Link 30 → Head → [30 | *] → [20 | *]
- Pop 10 → Link 20 → Head → [30 | *] → [20 | *] → [10 | NULL]
Final Reversed Linked List:
Head → [30 | *] → [20 | *] → [10 | NULL]
Code Implementation For Stack-based Approach To Reverse A Linked List
In this section, we will look at the code implementation of this approach to reverse a linked list in three languages: C++, Python, and Java.
Stack-based Approach To Reverse A Linked List C++ Example
#include <iostream>
#include <stack>
using namespace std;
struct Node {
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
Node* reverseUsingStack(Node* head) {
if (head == NULL || head->next == NULL)
return head;
stack<Node*> nodeStack;
Node* temp = head;
// Push all nodes onto the stack
while (temp != NULL) {
nodeStack.push(temp);
temp = temp->next;
}
// New head is the last node pushed (top of stack)
head = nodeStack.top();
nodeStack.pop();
temp = head;
// Pop nodes and reconstruct the list
while (!nodeStack.empty()) {
temp->next = nodeStack.top();
nodeStack.pop();
temp = temp->next;
}
// Set next of last node to NULL
temp->next = NULL;
return head;
}
// Utility function to print the linked list
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main() {
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
cout << "Original List: ";
printList(head);
head = reverseUsingStack(head);
cout << "Reversed List: ";
printList(head);
return 0;
}
Output:
Original List: 10 20 30
Reversed List: 30 20 10
Code Explanation:
- Node Structure: We define a Node structure with data (stores value) and next (points to the next node).
- It also contains a constructor that initializes a new node with a given value and sets next = NULL.
- We will use this to create a linked list that we will then reverse.
- Function reverseUsingStack(Node* head): Then, we define a function to reverse a linked list as follows:
- We first check if the list is empty (head == NULL) or has only one node (head->next == NULL). In this case the function returns the head as it's already reversed.
- If the condition for the if-statement is not met, we create a stack of Node pointers (nodeStack) to store all nodes.
- Push All Nodes onto the Stack: Then we create a temporary pointer temp to traverse the list and assign the head node to it.
- Then, as mentioned in code comments, we push each node onto the stack (nodeStack.push(temp)).
- Pop Nodes and Reconstruct the Reversed List:
- Set head = nodeStack.top() → The last node pushed becomes the new head.
- Pop nodes from the stack and reassign next pointers to reverse the links.
- Stop when the stack is empty and ensure the last node's next is set to NULL to mark the end of the reversed list.
- Main Execution: We create a linked list with three nodes linked together (10 → 20 → 30) and print it using printList(head).
- Then, we call reverseUsingStack(head) to reverse the list and print that to the console.
This ensures a time complexity of O(n) (traversing and pushing each node once) and a space complexity of O(n) (due to stack storage).
Stack-based Approach To Reverse A Linked List Python Example
class Node:
def __init__(self, data):
self.data = data
self.next = None
def reverse_using_stack(head):
if not head or not head.next:
return head
stack = []
temp = head
# Push all nodes onto the stack
while temp:
stack.append(temp)
temp = temp.next
# New head is the last node pushed (top of stack)
head = stack.pop()
temp = head
# Pop nodes and reconstruct the reversed list
while stack:
temp.next = stack.pop()
temp = temp.next
temp.next = None # Ensure last node points to NULL
return head
# Utility function to print the linked list
def print_list(head):
while head:
print(head.data, end=" ")
head = head.next
print()
# Creating and reversing the linked list
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
print("Original List:", end=" ")
print_list(head)
head = reverse_using_stack(head)
print("Reversed List:", end=" ")
print_list(head)
Code Explanation:
- Node Class: We define a Node class with attributes data (stores the value) and next (points to the next node). It also has a constructor that initializes data and sets next to None.
- Function reverse_using_stack(head): Then, we have a function to reverse a linked list as follows:
- Using an if-statement, we check if the list is empty or has one node. In either case the functionr returns head.
- If the condition is not met, we use a list as a stack to store node references.
- Push All Nodes onto the Stack: Then, we traverse the list using a while loop, and in every iteration, we push each node onto the stack using the append() function.
- Pop Nodes and Reconstruct the Reversed List:
- Pop the top node and set it as the new head.
- Continue popping and updating next pointers to reconstruct the reversed list.
- Ensure the last node's next is set to None to mark the end.
- Main Execution: Then, we create a linked list with three nodes (10 → 20 → 30) and print it using print_list(head).
- Next, we call the function reverse_using_stack(head) to reverse the list and also print it to the console.
Stack-based Approach To Reverse A Linked List Java Example
import java.util.Stack;
class Node {
int data;
Node next;
Node(int val) {
data = val;
next = null;
}
}
public class Main {
public static Node reverseUsingStack(Node head) {
if (head == null || head.next == null)Â
return head;
Stack<Node> stack = new Stack<>();
Node temp = head;
// Push all nodes onto the stack
while (temp != null) {
stack.push(temp);
temp = temp.next;
}
// New head is the last node pushed (top of stack)
head = stack.pop();
temp = head;
// Pop nodes and reconstruct the reversed list
while (!stack.isEmpty()) {
temp.next = stack.pop();
temp = temp.next;
}
temp.next = null;Â // Ensure last node points to NULL
return head;
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
System.out.print("Original List: ");
printList(head);
head = reverseUsingStack(head);
System.out.print("Reversed List: ");
printList(head);
}
}
Code Explanation:
- Node Class: Defines a Node class with attributes data (stores the value) and next (points to the next node).
- It also contains a constructor that initializes data and sets next to null.
- Function reverseUsingStack(Node head): We define a function that reverses a linked list as follows:
- We first check if the list is empty or has one node. If so, it returns head.
- If not, we create a Stack to store node references.
- Push All Nodes onto the Stack: Then we traverse the list using while loop and push each node onto the stack.
- Pop Nodes and Reconstruct the Reversed List:
- Pop the top node and set it as the new head.
- Continue popping and updating next pointers to reconstruct the reversed list.
- Ensure the last node's next is set to null to mark the end.
- Main Execution: We create a linked list (10 → 20 → 30) and print it to the console printList(head).
- Then, we reverse the linked list using reverseUsingStack(head) and print it.
Complexity Analysis Of Different Approaches To Reverse A Linked List
Each method to reverse a linked list has different time and space complexities. Below is a comparison of the three approaches:
Approach |
Time Complexity |
Space Complexity |
Reason |
Recursive |
O(n) |
O(n) |
Each recursive call adds a function to the call stack. |
Iterative |
O(n) |
O(1) |
Uses only a few pointers without extra memory. |
Using Stack |
O(n) |
O(n) |
Requires extra stack memory to store all nodes. |
Key Takeaways:
- Fastest Approach: All three methods run in O(n) time complexity since every node is processed once.
- Most Memory-Efficient:
- Iterative Approach (O(1) space) is the best as it does not use additional memory beyond a few pointers.
- Recursive Approach (O(n) space) is inefficient for large lists due to function call stack usage.
- Stack-Based Approach (O(n) space) is also memory-heavy since it stores all nodes in an explicit stack.
Conclusion
Reversing a linked list is a fundamental operation with three main approaches:
- Recursive Approach: Uses the call stack to reverse pointers but consumes extra memory.
- Iterative Approach: The most efficient method, using only a few pointers to swap links in O(1) space.
- Stack-Based Approach: Stores all nodes in a stack before reconstructing the list in reverse, making it intuitive but memory-intensive.
For optimal performance in interviews and real-world applications, the iterative approach is preferred due to its efficiency. However, understanding all three methods to reverse a linked list strengthens problem-solving skills and prepares you for variations of linked list-related problems.
Frequently Asked Questions
Q1. Can I reverse a linked list without using extra space?
Yes! The iterative approach reverses a linked list in-place using only a few pointers (prev, curr, next), making it the most memory-efficient method with O(1) space complexity.
Q2. Which approach is best for reversing a linked list?
The iterative approach is the best in terms of efficiency because it runs in O(n) time and uses O(1) space. The recursive and stack-based approaches require additional memory, making them less optimal.
Q3. What happens if I reverse a linked list twice?
If you reverse a linked list twice, it will return to its original order. Example:
- Original: 10 → 20 → 30
- Reversed: 30 → 20 → 10
- Reversed Again: 10 → 20 → 30
Q4. Can I reverse a doubly linked list using the same methods?
Yes, but with modifications. In a doubly linked list, you need to swap both next and prev pointers for each node instead of just next.
Q5. Is reversing a linked list in O(log n) time possible?
No, because each node must be visited at least once to update pointers, making O(n) the best possible time complexity.
By now you must know how to reverse a linked list with ease. Here are a few more blogs you must explore:
- Doubly Linked List Data Structure | All Operations Explained (+Codes)
- Graph Data Structure | Types, Algorithms & More (+Code Examples)
- What Is Linear Search? Algorithm, Working, Complexity & Examples
- Advantages And Disadvantages Of Linked Lists Summed Up For You
- 53 Frequently Asked Linked List Interview Questions With Answers 2025
An economics graduate with a passion for storytelling, I thrive on crafting content that blends creativity with technical insight. At Unstop, I create in-depth, SEO-driven content that simplifies complex tech topics and covers a wide array of subjects, all designed to inform, engage, and inspire our readers. My goal is to empower others to truly #BeUnstoppable through content that resonates. When I’m not writing, you’ll find me immersed in art, food, or lost in a good book—constantly drawing inspiration from the world around me.
Comments
Add commentLogin to continue reading
And access exclusive content, personalized recommendations, and career-boosting opportunities.

Subscribe
to our newsletter
Siddhi Raney 1 day ago
Amar kumar Giri 2 days ago
Divyansh Shrivastava 3 days ago
Archana Ba Parmar 6 days ago
Paritosh Sharma 2 weeks ago
Mihir Kumar Ranjan 2 weeks ago