.png)
Reverse a Singly Linked List
Reversing a singly linked list is one of the most fundamental and frequently asked linked list problems in data structures and technical interviews.
This problem tests your understanding of pointer manipulation, traversal logic, and memory structure in linked lists.
Problem Statement
Given the head pointer of a singly linked list, reverse the linked list and return the new head of the reversed list.
Example:
Input:
10 → 20 → 30 → 40 → NULL
Output:
40 → 30 → 20 → 10 → NULL
Understanding the Structure of a Singly Linked List
Each node contains:
- Data
- Pointer to next node
Structure:
[ Data | Next ]
In a singly linked list, traversal is possible only in forward direction.
Therefore, reversing requires careful pointer re-linking.
Observational Thinking Before Writing Code
Let us analyze what reversing actually means.
Original:
Head
↓
10 → 20 → 30 → NULL
After reversing:
Head
↓
30 → 20 → 10 → NULL
What changes?
The direction of every link changes.
Originally:
10.next = 20
20.next = 30
30.next = NULL
After reversing:
30.next = 20
20.next = 10
10.next = NULL
Key Insight:
We must reverse each pointer one by one while traversing.
We cannot lose track of the next node while changing links.
Approach Using Iterative Method
Core Idea
Use three pointers:
- prev
- current
- next
Steps:
- Initialize prev = NULL
- Set current = head
- While current is not NULL:
- Store next = current->next
- Reverse current->next = prev
- Move prev = current
- Move current = next
- At end, prev becomes new head
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(1)
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
struct Node* 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;
}
return prev;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 30;
head->next->next->next = NULL;
printf("Original List:\n");
printList(head);
head = reverse(head);
printf("Reversed List:\n");
printList(head);
return 0;
}Output:
Original List:
10 -> 20 -> 30 -> NULL
Reversed List:
30 -> 20 -> 10 -> NULL
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
Node* reverse(Node* head) {
Node* prev = NULL;
Node* current = head;
Node* next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " -> ";
head = head->next;
}
cout << "NULL" << endl;
}
int main() {
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
cout << "Original List:" << endl;
printList(head);
head = reverse(head);
cout << "Reversed List:" << endl;
printList(head);
return 0;
}
Output:
Original List:
10 -> 20 -> 30 -> NULL
Reversed List:
30 -> 20 -> 10 -> NULL
Java Implementation
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
static Node reverse(Node head) {
Node prev = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
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.println("Original List:");
printList(head);
head = reverse(head);
System.out.println("Reversed List:");
printList(head);
}
}
Output:
Original List:
10 -> 20 -> 30 -> NULL
Reversed List:
30 -> 20 -> 10 -> NULL
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def reverse(head):
prev = None
current = head
while current is not None:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
def print_list(head):
while head is not None:
print(head.data, end=" -> ")
head = head.next
print("NULL")
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
print("Original List:")
print_list(head)
head = reverse(head)
print("Reversed List:")
print_list(head)
Output:
Original List:
10 -> 20 -> 30 -> NULL
Reversed List:
30 -> 20 -> 10 -> NULL
Recursive Approach to Reverse a Singly Linked List
Conceptual Understanding
Recursive logic:
If head is NULL or head.next is NULL
→ return head
Otherwise:
- Reverse the rest of the list
- Make head.next.next = head
- Set head.next = NULL
- Return new head
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(n) due to recursion stack
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
// Define Node FIRST
struct Node {
int data;
struct Node* next;
};
// Recursive reverse function
struct Node* reverseRecursive(struct Node* head) {
if (head == NULL || head->next == NULL)
return head;
struct Node* newHead = reverseRecursive(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
// Print list
void printList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
int main() {
// Create list: 10 -> 20 -> 30
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 30;
head->next->next->next = NULL;
printf("Original List:\n");
printList(head);
head = reverseRecursive(head);
printf("Reversed List:\n");
printList(head);
return 0;
}(Use same print and main from above, replace reverse call)
Output:
Original List:
10 -> 20 -> 30 -> NULL
Reversed List:
30 -> 20 -> 10 -> NULL
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
// Define Node class FIRST
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
// Recursive reverse function
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;
}
// Print function
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " -> ";
head = head->next;
}
cout << "NULL" << endl;
}
int main() {
// Create list: 10 -> 20 -> 30
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
cout << "Original List:" << endl;
printList(head);
head = reverseRecursive(head);
cout << "Reversed List:" << endl;
printList(head);
return 0;
}
Output:
Original List:
10 -> 20 -> 30 -> NULL
Reversed List:
30 -> 20 -> 10 -> NULL
Java Implementation
class Node {
int data;
Node next;
Node(int val) {
data = val;
next = null;
}
}
public class Main {
// Recursive reverse function
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;
}
// Print list
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) {
// Create list: 10 -> 20 -> 30
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
System.out.println("Original List:");
printList(head);
head = reverseRecursive(head);
System.out.println("Reversed List:");
printList(head);
}
}Output:
Original List:
10 -> 20 -> 30 -> NULL
Reversed List:
30 -> 20 -> 10 -> NULL
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Recursive reverse function
def reverse_recursive(head):
if head is None or head.next is None:
return head
new_head = reverse_recursive(head.next)
head.next.next = head
head.next = None
return new_head
# Print list
def print_list(head):
while head is not None:
print(head.data, end=" -> ")
head = head.next
print("NULL")
# Main
if __name__ == "__main__":
# Create list: 10 -> 20 -> 30
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
print("Original List:")
print_list(head)
head = reverse_recursive(head)
print("Reversed List:")
print_list(head)Output:
Original List:
10 -> 20 -> 30 -> NULL
Reversed List:
30 -> 20 -> 10 -> NULL
Final Comparison
| Approach | Time | Space | Recommended |
|---|---|---|---|
| Iterative | O(n) | O(1) | Yes |
| Recursive | O(n) | O(n) | For learning |
This completes the detailed article on reversing a singly linked list.
Next Problem in the series-
Reverse a Doubly Linked List
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
