Reverse Linked List
Learn to reverse a singly linked list using both iterative and recursive approaches. Master pointer manipulation fundamentals.
Problem Statement
Given the head of a singly linked list, reverse the list, and return the reversed list.
Examples
Approach
Iterative Approach:
Initialize Pointers
Start with prev = null and current = head
Iterate Through List
For each node, save the next node, reverse the current node's pointer to point to prev, then move both pointers forward.
Return New Head
When iteration completes, prev will point to the new head of the reversed list.
Recursive Approach:
Base Case
If the list is empty or has only one node, return the head.
Recursive Call
Recursively reverse the rest of the list starting from head.next.
Reverse Links
Make the next node point back to the current node, then set current node's next to null.
Solution
// Definition for singly-linked list node
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
// Iterative Solution
function reverseList(head) {
let prev = null;
let current = head;
while (current !== null) {
// Save next node
let nextTemp = current.next;
// Reverse the pointer
current.next = prev;
// Move pointers forward
prev = current;
current = nextTemp;
}
return prev; // New head
}
// Recursive Solution
function reverseListRecursive(head) {
// Base case
if (head === null || head.next === null) {
return head;
}
// Recursive call
let newHead = reverseListRecursive(head.next);
// Reverse the links
head.next.next = head;
head.next = null;
return newHead;
}Complexity Analysis
Iterative Approach:
O(n)We visit each node exactly once.
O(1)Only using a constant amount of extra space for pointers.
Recursive Approach:
O(n)We visit each node exactly once.
O(n)Due to the recursion call stack, which can go n levels deep.
Ready for More Challenges?
Continue mastering linked list operations with more problems.