LinkedListProblem 1 of 36
Write a Program to reverse the Linked List (Both Iterative and recursive)
Reverse a Linked List - Iterative and Recursive
Problem Statement
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example
Input: head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]
Input: head = [1, 2]
Output: [2, 1]
Input: head = []
Output: []
Brute Force Approach (Using Stack/Recursion)
Intuition
The recursive approach uses the call stack to reverse the linked list. We recursively reach the end of the list, and while backtracking, we reverse the links.
Algorithm
- Base case: If head is NULL or only one node, return head
- Recursively reverse the rest of the list
- Make the next node point back to current node
- Set current node's next to NULL
Implementation
Complexity Analysis
- Time Complexity: O(n) - We visit each node once
- Space Complexity: O(n) - Recursive call stack uses O(n) space
Optimal Approach (Iterative)
Intuition
We can reverse the linked list in-place by changing the next pointers of each node. We use three pointers: previous, current, and next to reverse the links one by one.
Algorithm
- Initialize three pointers: prev = NULL, curr = head, next = NULL
- Traverse the list and for each node:
- Store the next node
- Reverse the current node's pointer
- Move prev and curr one step forward
- Return prev as the new head
Visualization
Initial: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
↑
curr
prev = NULL
Step 1: NULL <- 1 2 -> 3 -> 4 -> 5 -> NULL
↑ ↑
prev curr
Step 2: NULL <- 1 <- 2 3 -> 4 -> 5 -> NULL
↑ ↑
prev curr
...and so on until:
Final: NULL <- 1 <- 2 <- 3 <- 4 <- 5
↑
prev (new head)
Implementation
Complexity Analysis
- Time Complexity: O(n) - We visit each node exactly once
- Space Complexity: O(1) - Only using constant extra space for pointers
Key Takeaways
- Iterative approach is preferred in interviews due to O(1) space complexity
- Recursive approach is elegant but uses O(n) stack space
- The key insight is to save the next pointer before modifying the current node's next
- Always handle edge cases: empty list and single node list
- This is a fundamental problem - many linked list problems build upon reversing