35.Reverse Linked List

EasyBlind 75Linked List · 1/11

Problem

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

After reversing, the node that used to be last becomes the first, and every next pointer points to the node that used to come before it.

Examples

Input:  head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]
Explanation: Every arrow flips direction; node 5 becomes the new head.

Input:  head = [1, 2]
Output: [2, 1]

Input:  head = []
Output: []
Explanation: An empty list reversed is still empty.

Constraints

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

💡 Key Insight

Reversing a list means flipping each next pointer to point backwards. If you walk the list once while remembering the previous node, you can flip one arrow at a time — the only trick is to save curr.next before overwriting it, otherwise you lose the rest of the list.

Brute Force (Stack)

TimeO(n)SpaceO(n)

Intuition

A stack is last-in, first-out, so pushing every node and then popping them gives the nodes in reverse order. We then relink them in the popped order.

Algorithm

Push every node onto a stack.
Pop the top node — it is the new head.
Keep popping, setting tail.next = popped and advancing tail.
Set the final tail.next = null (the old head still points to the old second node, which would create a cycle).
Return the new head.

Visualization

list:  1 -> 2 -> 3
stack (top on right): [1, 2, 3]

pop 3 -> head = 3
pop 2 -> 3 -> 2
pop 1 -> 3 -> 2 -> 1 -> null   (must clear 1.next!)

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        Deque<ListNode> stack = new ArrayDeque<>();
        for (ListNode node = head; node != null; node = node.next) {
            stack.push(node);
        }
        ListNode newHead = stack.pop();
        ListNode tail = newHead;
        while (!stack.isEmpty()) {
            tail.next = stack.pop();
            tail = tail.next;
        }
        tail.next = null; // old head is now the tail; break the old link
        return newHead;
    }
}

Complexity

Time: O(n) — every node is pushed and popped once.
Space: O(n) — the stack holds all n nodes.

Recursion

TimeO(n)SpaceO(n)

Intuition

Trust the recursion to reverse everything after head. When it returns, head.next is now the tail of the reversed sublist, so we just hang head after it: head.next.next = head, then cut head.next = null.

Algorithm

Base case: if head is null or head.next is null, return head.
newHead = reverseList(head.next).
head.next.next = head — the node after head now points back to it.
head.next = null — head becomes the new tail.
Return newHead (the original last node, unchanged through every level).

Visualization

reverseList(1)
  reverseList(2)
    reverseList(3) -> returns 3 (base case)
  2.next(=3).next = 2, 2.next = null   => 3 -> 2
1.next(=2).next = 1, 1.next = null     => 3 -> 2 -> 1

Code

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head; // empty list or last node: it is the new head
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head; // the next node points back to head
        head.next = null;      // head becomes the tail of the reversed part
        return newHead;
    }
}

Complexity

Time: O(n) — one call per node.
Space: O(n) — recursion depth equals the list length (5000 frames is fine, but this is not O(1)).

Iterative Pointer ReversalOptimal

TimeO(n)SpaceO(1)

Intuition

Walk the list with two pointers: prev (already-reversed part) and curr (next node to flip). At each step save curr.next, point curr back at prev, then shift both pointers forward. When curr falls off the end, prev is the new head.

Algorithm

prev = null, curr = head.
While curr != null:
- next = curr.next (save the rest of the list).
- curr.next = prev (flip the arrow).
- prev = curr, curr = next (advance).
Return prev.

Dry Run

flowchart TD
    S0["start: prev=null, curr=1<br/>1 -> 2 -> 3 -> null"] --> S1["flip 1: null <- 1<br/>prev=1, curr=2"]
    S1 --> S2["flip 2: null <- 1 <- 2<br/>prev=2, curr=3"]
    S2 --> S3["flip 3: null <- 1 <- 2 <- 3<br/>prev=3, curr=null"]
    S3 --> R["curr is null: return prev = 3<br/>3 -> 2 -> 1 -> null"]

Code

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next; // save the rest before overwriting
            curr.next = prev;          // flip the pointer
            prev = curr;
            curr = next;
        }
        return prev; // prev is the old tail = new head
    }
}

Complexity

Time: O(n) — each node is visited once.
Space: O(1) — only three pointers.

Complexity Comparison

Approach	Time	Space
Stack	O(n)	O(n)
Recursion	O(n)	O(n)
Iterative Pointer Reversal	O(n)	O(1)

Common Pitfalls

Overwriting curr.next before saving it — the rest of the list becomes unreachable.
Returning curr instead of prev at the end — curr is always null when the loop stops.
In the recursive version, forgetting head.next = null, which leaves a 2-node cycle between the old first and second nodes.
In the stack version, not clearing the last node's next, which also creates a cycle.
Not handling head == null — every approach must return null for an empty list.