Reverse Linked List

EasyLinked ListRecursion
Category: Linked List
Companies that ask this question:
AmazonMicrosoftFacebookGoogleApple

Approach

Reverse Linked List

Problem Statement

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

Examples

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

Constraints

  • The number of nodes in the list is the range [0, 5000]
  • -5000 <= Node.val <= 5000

Approach

Solution 1: Iterative (Optimal)

The key idea is to reverse the pointers one by one while traversing the list.

Algorithm:

  1. Use three pointers: prev (initially null), curr (head), and next
  2. While curr is not null:
    • Save next = curr.next (before we lose it)
    • Reverse the pointer: curr.next = prev
    • Move pointers forward: prev = curr, curr = next
  3. Return prev (new head)

Example Walkthrough:

Initial: 1 → 2 → 3 → 4 → 5 → null
         ↑
        curr

Step 1:  null ← 1   2 → 3 → 4 → 5 → null
              ↑     ↑
             prev  curr

Step 2:  null ← 1 ← 2   3 → 4 → 5 → null
                    ↑   ↑
                  prev curr

Step 3:  null ← 1 ← 2 ← 3   4 → 5 → null
                        ↑   ↑
                      prev curr

... continue until curr = null

Final:   null ← 1 ← 2 ← 3 ← 4 ← 5
                                ↑
                              prev (new head)

Solution 2: Recursive

Recursively reverse the rest of the list, then fix the pointers.

Algorithm:

  1. Base case: if head is null or single node, return head
  2. Recursively reverse rest: newHead = reverseList(head.next)
  3. Fix pointers: head.next.next = head
  4. Set head.next = null
  5. Return newHead

Complexity Analysis

Iterative:

  • Time Complexity: O(n) - single pass through the list
  • Space Complexity: O(1) - only a few pointers

Recursive:

  • Time Complexity: O(n) - visit each node once
  • Space Complexity: O(n) - recursion call stack

Pattern Recognition

This problem demonstrates:

  • Pointer manipulation - the core of linked list problems
  • Three-pointer technique - prev, curr, next
  • Iterative vs Recursive trade-offs - space vs clarity
  • Foundation for many linked list problems

Solution

java
1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5    int val;
6    ListNode next;
7    ListNode() {}
8    ListNode(int val) { this.val = val; }
9    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
10}
11
12class Solution {
13    // Solution 1: Iterative (Optimal - O(1) space)
14    public ListNode reverseList(ListNode head) {
15        // Use three pointers: prev, curr, next
16        ListNode prev = null;
17        ListNode curr = head;
18
19        // Traverse the list and reverse pointers
20        while (curr != null) {
21            // Save next node before we lose it
22            ListNode next = curr.next;
23
24            // Reverse the pointer
25            curr.next = prev;
26
27            // Move pointers forward
28            prev = curr;
29            curr = next;
30        }
31
32        // prev is now the new head
33        return prev;
34    }
35
36    // Solution 2: Recursive
37    public ListNode reverseListRecursive(ListNode head) {
38        // Base cases
39        if (head == null || head.next == null) {
40            return head;
41        }
42
43        // Recursively reverse the rest of the list
44        ListNode newHead = reverseListRecursive(head.next);
45
46        // Fix the pointers
47        // head.next is now the last node in reversed portion
48        // Make it point back to current head
49        head.next.next = head;
50
51        // Current head is now the tail, point to null
52        head.next = null;
53
54        return newHead;
55    }
56}
57
Loading visualizer...