Reverse a linked list
Problem
Given the head of a singly linked list, reverse it and return the new head. Be ready to write it both iteratively and recursively.
Example 1
Input: 1 → 2 → 3 → 4 → 5 Output: 5 → 4 → 3 → 2 → 1
Also asked as: Write a Program to reverse the Linked List. (Both Iterative and recursive)
Test cases
Case 1
Input: [1,2,3,4,5] Expected: [5,4,3,2,1]
Case 2
Input: [1,2] Expected: [2,1]
Case 3
Input: [] Expected: []
View solutionHide solution2 approaches
1. Iterative (three pointers)
Time O(n)Space O(1)
Walk the list re-pointing each node’s next to the previous node.
function reverse(head) { let prev = null, cur = head; while (cur) { const next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev;}2. Recursive
Time O(n)Space O(n) call stack
Reverse the rest, then make the next node point back to the current one.
function reverse(head) { if (!head || !head.next) return head; const newHead = reverse(head.next); head.next.next = head; head.next = null; return newHead;}