Reverse a linked list

Easy

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: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}