☕ DSA Java Articles

Topics › Linked List › Medium Problems of LL

Reverse a LinkedList [Iterative]

Medium TUF ID 2850 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the head of a singly linked list. Reverse the list and return the new head. Walking forward from the returned head must visit the original values from last to first, and the original head must now be the tail with next == null. The ideal solution rewires the existing nodes in one pass using constant extra space; this article focuses on that iterative method, with the recursive version shown for comparison.

Constraints: 0 ≤ n ≤ 10^5 nodes, values fit in a 32-bit signed integer, no cycles.

Example 1

list = 1 -> 2 -> 3 -> 4 -> 5
answer = 5 -> 4 -> 3 -> 2 -> 1

Example 2

list = 1 -> 2
answer = 2 -> 1                // 2.next is 1, 1.next is null

Example 3

list = (empty)
answer = (empty)

The node type is the standard one with an int val and a ListNode next reference.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Approach 1: Brute force, reverse the values

Intuition. If only the sequence of values matters, the nodes can stay where they are and the values can be moved. A stack is a device that reverses order: push every value in a forward pass, then pop in a second forward pass and overwrite each node’s value. The first node receives the last value pushed, which belonged to the tail.

Algorithm.

  1. Traverse and push each val onto a stack.
  2. Traverse again from the head; at each node, pop the stack into val.
  3. Return the same head.
static ListNode bruteForce(ListNode head) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (ListNode t = head; t != null; t = t.next) stack.push(t.val);
    for (ListNode t = head; t != null; t = t.next) t.val = stack.pop();    // pops come out in reverse order
    return head;
}

Complexity. Time O(n): two passes. Space O(n) for the stack.

This passes any test that compares values, and the Java file checks it against the same expected output as the other approaches. But it does not reverse the list in the structural sense: the head node object is still the head (the tests assert bruteForce(same) == same). When other code holds references to particular nodes, or when the problem is a building block for group reversal or palindrome checking, the links themselves must change. The method also uses linear extra memory where none is needed.

Approach 2: Optimal, iterative pointer reversal

Intuition. Reversing a singly linked list means every node’s next should point at the node that used to come before it. A singly linked node does not know its predecessor, so we carry it along in a variable prev as we walk. At each node we redirect next to prev and then move forward. The one trap is that redirecting next destroys our only path to the rest of the list, so the old next must be saved into a temporary before the redirect. When the walk ends, prev is standing on the last node we processed, the old tail, which is the new head.

Algorithm.

  1. Set prev = null and current = head.
  2. While current != null:
    • save next = current.next;
    • set current.next = prev;
    • move prev = current and current = next.
  3. Return prev.
static ListNode optimal(ListNode head) {
    ListNode prev = null, current = head;
    while (current != null) {
        ListNode next = current.next;   // save the rest of the list before cutting the link
        current.next = prev;            // flip this node's pointer
        prev = current;                 // advance both pointers
        current = next;
    }
    return prev;                        // prev ends on the old tail, which is the new head
}

Complexity. Time O(n): each node is visited once with constant work. Space O(1): three references regardless of n.

Dry run on 1 -> 2 -> 3. Each row shows the state at the end of an iteration.

iteration current flipped its new next prev current moves to reversed part
1 1 null 1 2 1 -> null
2 2 1 2 3 2 -> 1 -> null
3 3 2 3 null 3 -> 2 -> 1 -> null

The loop ends with current == null and prev on node 3, which is returned. The old head 1 now has next == null, so it is the tail. The test file checks these facts on real node objects: newHead == oldTail, head.next == null, and newHead.next.next == head.

A useful way to see why the invariant holds: at the start of every iteration, prev is the head of a correctly reversed list made of all nodes already processed, and current is the head of the untouched remainder. The body moves exactly one node from the front of the remainder to the front of the reversed list, which is the insert-at-head operation. After n moves the remainder is empty and the reversed list is complete.

The first assignment prev = null is what makes the old head become the tail: its next is set to prev while prev is still null. The empty list needs no special case: current starts as null, the loop does not run, and prev = null is returned. A single node has its next set to null (unchanged) and is returned.

Reversing twice must restore the original order, and the tests do that on every input as a cheap consistency check.

For comparison: the recursive version

Intuition. Recursion expresses the same idea from the other end. Assume the rest of the list (from the second node onward) has already been reversed and its new head returned. The old second node is now the tail of that reversed part, and head should hang behind it: head.next.next = head. Then head becomes the overall tail, so its own next is cleared. The base case is a list of zero or one node, which is its own reverse.

Algorithm.

  1. If head is null or has no successor, return head.
  2. Let newHead = recursive(head.next).
  3. Set head.next.next = head and head.next = null.
  4. Return newHead.
static ListNode recursive(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = recursive(head.next);
    head.next.next = head;              // the old second node now points back at head
    head.next = null;                   // head becomes the tail
    return newHead;
}

Complexity. Time O(n). Space O(n) on the call stack, one frame per node, because the pointer fix-up happens after the recursive call returns.

That stack is the reason the iterative version is the one to write. The default Java thread stack handles a few thousand frames (the tests use 5000), but a list of 10^5 nodes risks StackOverflowError. The iterative loop has no such limit; the tests run it, and the brute force, on 200000 nodes.

Edge cases and pitfalls