Reversing a linked list is a common coding problem. Here, we explore all three approaches– recursive, iterative & stack-based, with step-by-step explanations and code implementations.

20 mins read

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:

Visual representation of reversed linked list.

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.