☕ DSA Java Articles

Topics › Linked List › Medium Problems of LL

Reverse a LL

Medium TUF ID 627 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the head of a singly linked list. Reverse the list so that the last node becomes the first, every next pointer points the other way, and the old head becomes the tail (its next is null). Return the new head. The reversal must keep the same node objects; only the links (or, in the brute-force version, the values) move.

Constraints: 0 ≤ n ≤ 5000 nodes in the LeetCode version, values fit in a 32-bit signed integer. The list has no cycle.

The node type used throughout is the usual one:

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

Example 1

head = 1 -> 2 -> 3 -> 4 -> 5
answer = 5 -> 4 -> 3 -> 2 -> 1      // every arrow flipped; 5 is the new head

Example 2

head = 1 -> 2
answer = 2 -> 1                     // two nodes simply swap roles

Example 3

head = (empty)
answer = (empty)                    // nothing to reverse; return null

Approach 1: Brute force

Intuition. If we are allowed to move values instead of links, a stack does the job: push every value while walking forward, then walk forward again and pop. A stack returns items in last-in first-out order, so the first node receives the last value, the second node the second-to-last value, and so on. The node chain itself is never touched.

Algorithm.

  1. Walk the list from head and push each val onto a stack.
  2. Walk the list again from head; at each node, pop the stack and store the popped value in the node.
  3. Return head (the node chain is unchanged, only the values moved).
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 last-in first-out
    return head;
}

Complexity. Time O(n): two passes over n nodes with constant work per node. Space O(n): the stack holds every value.

This is a legitimate answer when a problem says “reverse the values”, but interviewers usually mean “reverse the links”. Returning the same head object with rewritten contents also breaks any code that still holds a reference to a specific node and expects its value to be stable. The real question is how to do it without extra memory.

Approach 2: Optimal, iterative three-pointer reversal

Intuition. Reversing the list means every node’s next must point to the node that came before it. A singly linked node does not know its predecessor, so we carry it along in a variable prev while walking. The trap is that overwriting current.next destroys our only way to reach the rest of the list, so we must save current.next in a temporary before flipping. With prev, current and next we need exactly three pointers and no extra memory.

Algorithm.

  1. Set prev = null and current = head.
  2. While current is not null:
    • next = current.next (save the rest of the list).
    • current.next = prev (flip the link).
    • prev = current, current = next (advance).
  3. When the loop ends, current is null and prev is the old tail, which is the new head. Return prev.

The loop invariant is what makes this correct: before each iteration, all nodes from the original head up to prev are already reversed and end at prev, and current starts the untouched suffix. Each iteration moves exactly one node from the untouched suffix onto the reversed prefix.

static ListNode optimalIterative(ListNode head) {
    ListNode prev = null, current = head;
    while (current != null) {
        ListNode next = current.next;   // remember the rest before cutting the link
        current.next = prev;            // flip the pointer backwards
        prev = current;                 // advance both pointers
        current = next;
    }
    return prev;                        // the old tail is the new head
}

Dry run on 1 -> 2 -> 3:

step prev current next action
0 null 1 2 1.next = null; list so far: 1
1 1 2 3 2.next = 1; list so far: 2 -> 1
2 2 3 null 3.next = 2; list so far: 3 -> 2 -> 1
3 3 null   stop; return prev = 3

Complexity. Time O(n): each node is visited once and three assignments happen per visit. Space O(1): three pointers regardless of n.

An empty list works without a special case: the loop never runs and prev is null.

Approach 3: Optimal, recursive reversal

Intuition. Think of the list as head followed by the rest. If we could magically reverse the rest, we would get a chain whose last node is the node that used to be head.next. All that remains is to append head after that last node and make head the new tail. The recursion provides the magic: the base case is a list of zero or one node, which is already its own reverse.

The elegant trick is that after reversing the rest, head.next still points to the old second node, which is now the tail of the reversed part. So head.next.next = head appends head to that tail, and head.next = null makes head the new tail.

Algorithm.

  1. If head is null or head.next is null, return head.
  2. Let newHead = reverse(head.next); the sub-list after head is now reversed and head.next is its last node.
  3. Set head.next.next = head, then head.next = null.
  4. Return newHead unchanged. It is the original tail, found by the deepest call and passed all the way back up.
static ListNode optimalRecursive(ListNode head) {
    if (head == null || head.next == null) return head;   // empty list or single node: already reversed
    ListNode newHead = optimalRecursive(head.next);       // after this call, head.next is the tail of the reversed rest
    head.next.next = head;                                // the old second node now points back at head
    head.next = null;                                     // head becomes the new tail
    return newHead;
}

Complexity. Time O(n): one call per node. Space O(n) for the recursion stack, which is the price of the elegance. With n = 5000 the stack is fine on the default JVM; for lists of hundreds of thousands of nodes prefer the iterative version.

Both optimal methods return the same chain and are checked in the Java file against the same expected arrays; the test also confirms that reversing twice restores the original and that the returned head is the same object as the old tail.

Edge cases and pitfalls