Problem 8.1 · Linked ListsEasy

Reverse Linked List

What it teaches: The three-pointer reversal you'll reuse in palindrome checks, reordering and group reversal.

Practise it on judges as “Reverse Linked List”.

The problem

Given the head of a singly linked list, reverse it and return the new head.

Example 1

Input: head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]

Example 2

Input: head = []
Output: []

Constraints

0 ≤ number of nodes ≤ 5000

Pattern clues in the wording

→ Reverse the direction of links
→ O(1) extra space is possible

These clues point to In-Place Linked List Reversal: Walk the list with prev, curr and next, turning each arrow around as you go.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        return prev;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	head = [1,2,3,4,5]	[5,4,3,2,1]
2	head = [1,2]	[2,1]
3	head = []	[]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Recursive · O(n)2. Optimal: iterative three pointers · O(n)

Recursive

Time O(n) Space O(n) call stack

Reverse the rest, then make head.next point back to head and cut head.next.

Approach 1

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

Verdict: Short, but deep recursion on long lists risks a stack overflow.

Optimal: iterative three pointers

Time O(n) Space O(1)

prev = null, curr = head. Loop: save next, point curr back to prev, advance both. Return prev.

Approach 2

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

Verdict: The standard answer.

Before you submit

Edge cases and common mistakes

Test these inputs

Empty list
One node
Two nodes

Mistakes people make

Losing the rest of the list by not saving curr.next.
Returning the old head.

Interview

Follow-up questions

How would you reverse only positions m to n?

How would you reverse in groups of k?

Command Palette