Beginner LevelData Structures & Algorithms
How do you reverse a Singly Linked List iteratively and recursively?
ā Interview Prompt: Reverse a singly linked list in O(N) time and O(1) space iteratively, and O(N) space recursively.
Iterative (O(1) space ā preferred):
Maintain three pointers: prev, curr, next. Redirect each node's .next to prev, then advance all three pointers.
Recursive (O(N) call stack):
Recurse to the tail, then re-link pointers on the way back up.
Code Implementation Example
typescript
// Iterative ā O(N) time, O(1) space
function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
let curr = head;
while (curr) {
const next = curr.next; // save next
curr.next = prev; // reverse link
prev = curr; // advance prev
curr = next; // advance curr
}
return prev; // new head
}
// Recursive ā O(N) time, O(N) stack space
function reverseListRec(head: ListNode | null): ListNode | null {
if (!head || !head.next) return head;
const newHead = reverseListRec(head.next);
head.next.next = head; // reverse the link
head.next = null;
return newHead;
}š”Iterative (O(1) space) and recursive linked list reversal.
šÆ Interview Key Takeaway
Prefer iterative reversal for O(1) space. The three-pointer (prev, curr, next) pattern is fundamental for in-place linked list manipulation.
#DSA#Linked List#Reversal#Iterative#Beginner
Back to all Data Structures & Algorithms Questionsā