Reverse Linked List
Learn to reverse a singly linked list using both iterative and recursive approaches. Master pointer manipulation fundamentals.
EasyTime O(n) · Space O(1) iterative
Problem statement
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1
Input: head = [1, 2, 3, 4, 5] Output: [5, 4, 3, 2, 1]
Example 2
Input: head = [1, 2] Output: [2, 1]
Example 3
Input: head = [] Output: []
Approach
Iterative approach
- 1Initialize pointers. Start with
prev = nullandcurrent = head. - 2Iterate through the list. For each node, save the next node, reverse the current node's pointer to point to prev, then move both pointers forward.
- 3Return the new head. When iteration completes, prev points to the new head of the reversed list.
Recursive approach
- 1Base case. If the list is empty or has only one node, return the head.
- 2Recursive call. Recursively reverse the rest of the list starting from head.next.
- 3Reverse links. Make the next node point back to the current node, then set the current node's next to null.
Solution
JavaScript
// 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;
}Time & space complexity
Iterative approach
Time complexity
O(n)
We visit each node exactly once.
Space complexity
O(1)
Only a constant amount of extra space for pointers.
Recursive approach
Time complexity
O(n)
We visit each node exactly once.
Space complexity
O(n)
Due to the recursion call stack, which can go n levels deep.
Discussion
Questions, ideas or a different approach? Join the conversation.