Reverse a linked list by changing links between nodes
Reverse a linked list by changing links between nodes
Reverse a Linked List is one of the most commonly asked interview questions for data structures. It helps developers understand how pointers or references work in linked lists.
In this article, we will discuss how to reverse a singly linked list by changing links between nodes, using Java. This article covers:
- How to reverse a linked list ?
- Detailed algorithm explanation
- Java code implementation (iterative and recursive)
Each node contains two parts:
1. Data: stores the actual value.
2. Next: Reference or pointer to the next node in the list.
What Does Reverse a Linked List Mean?
Reversing a linked list means changing the direction of the next pointers so that:
1 -> 2 -> 3 -> 4 -> null
becomes:
4 -> 3 -> 2 -> 1 -> null
We do not create a new list or use any array. Instead, we manipulate the links between existing nodes.
Approach To Reverse a Linked List
There are two main approaches to reverse a singly linked list:
- Iterative Method: using loop and pointer manipulation.
- Recursive Method: using function call stack.
Node Structure in Java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
Method 1: Iterative Approach to Reverse a Linked List
Algorithm:
- Initialize three pointers:
prev as null
curr as head
next as null (temporary holder)
Loop while curr is not null:
Store curr.next in next
Change curr.next to point to prev
Move prev to curr
Move curr to next
Set head = prev (new head)
Space Complexity: O(1), as no extra space is used.
Code:
public class LinkedListReversal {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
// Function to reverse the linked list
public static Node reverseIterative(Node head) {
Node prev = null;
Node curr = head;
Node next;
while (curr != null) {
next = curr.next; // Step 1: store next
curr.next = prev; // Step 2: reverse pointer
prev = curr; // Step 3: move prev forward
curr = next; // Step 4: move curr forward
}
return prev; // New head
}
// Function to print list
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
// Example usage
public static void main(String[] args) {
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);
System.out.print("Original List: ");
printList(head);
head = reverseIterative(head);
System.out.print("Reversed List: ");
printList(head);
}
}
Input:
Original List: 10 20 30 40
Output:
Reversed List: 40 30 20 10
Method 2: Recursive Approach to Reverse a Linked List
Algorithm:
- If head is null or only one node, return it.
- Recursively call reverse on head.next.
- Change head.next.next to point to head.
- Set head.next = null.
- Return the new head.
Space Complexity: O(n) due to recursive stack.
Code:
public class RecursiveReverse {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
public static Node reverseRecursive(Node head) {
// Base condition
if (head == null || head.next == null)
return head;
// Recur for the rest of the list
Node rest = reverseRecursive(head.next);
// Change links
head.next.next = head;
head.next = null;
return rest;
}
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(1);
head.next = new Node(3);
head.next.next = new Node(5);
head.next.next.next = new Node(7);
System.out.print("Original List: ");
printList(head);
head = reverseRecursive(head);
System.out.print("Reversed List: ");
printList(head);
}
}
Input:
Original List: 1 3 5 7
Output:
Reversed List: 7 5 3 1
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Edge Cases to Consider for Reverse of Linked List
- Empty List
Input: null
Output: null - Single Node List
Input: 5
Output: 5 - Already Reversed List
No harm; reversing twice restores original
Comparison between both methods:
| Feature | Iterative | Recursive |
|---|---|---|
| Time Complexity | O(n) | O(n) |
| Space Complexity | O(1) | O(n) due to stack |
| Simplicity | Easy to understand | Elegant but stack-heavy |
| Suitable for Large List? | Yes | No (risk of StackOverflow) |
Conclusion
Reversing a linked list by changing the links is a fundamental algorithm that demonstrates a deep understanding of pointer manipulation and memory management.
- Using Java, we explored both iterative and recursive approaches to solve the problem.
- Iterative method is space-efficient and preferred for large lists.
- Recursive method is elegant but uses stack space.
Understanding both methods strengthens your grasp on linked list operations and prepares you for technical interviews and real world problems.
FAQ's related to Reverse a linked list
Answer:
Yes. The iterative method reverses the list in place using O(1) space.
Answer:
Most efficient method to reverse a singly linked list in Java is using the iterative approach, which reverses the links between nodes in-place with a time complexity of O(n) and space complexity of O(1).
Answer:
Yes. By changing the next pointers of each node using an iterative approach, you can reverse a linked list in Java without using any additional data structure or space.
Answer:
In recursion, the reversal happens by recursively reaching the end of the list and then modifying the next pointers while the call stack unwinds. This method uses O(n) space due to the call stack and is more elegant but less memory efficient for large lists.
Answer:
Iterative approach is space efficient and faster for large lists, while the recursive method is cleaner but uses extra memory due to recursion.
Iterative reversal is preferred in production level code for large data sets.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment