DSA-049 · Linked list pointer mutation

Reverse Linked List

Foundation · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 506 deterministic checks. Learner drafts are not executed.

Understand the problem

Reverse a finite acyclic singly linked list in place and return the new head. Reuse the exact input node objects and reverse their next references; do not allocate replacement nodes or merely swap their values.

Input is null or the head of a finite acyclic list of at most 100,000 Node objects. Each node has a final int value and mutable Node next. A cyclic input is outside this contract.
Return null for an empty list. The old tail becomes the new head, and the old head has next=null. Preserve values and exactly the input node identities.
Both approaches mutate next links. The caller must use the returned head; any other reference to a node observes the changed links.

Examples

Input: a(1) → b(2) → c(3) → null
Output: c(3) → b(2) → a(1) → null
The returned object is c, not a new node with value 3. The old head a becomes the tail.
Input: a(5) → b(5) → null
Output: b(5) → a(5) → null
Equal values do not mean equal objects; the two identities must reverse.
Input: null
Output: null
No nodes and no mutations are needed.

Before you start

Node identity versus value equality
References, null and in-place mutation
Loop invariants for processed and unprocessed regions

Recognize the structure

The task changes links, not value order in an array. We need a reference to the reversed prefix and another to the unprocessed suffix. This is not sorting a list or copying it: both would have different identity and ordering requirements.

Try before revealing

Hint 1

Describe which part of the list is already reversed and which part remains untouched.

Hint 2

Which reference would be lost if you changed current.next immediately?

Hint 3

Save next, redirect current.next to previous, advance previous and current, then return previous.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Retain nodes on a stack

Traverse without mutating and push each Node reference onto a stack. Pop the last node as result and relink subsequent pops, finishing with tail.next=null. For a→b→c, popping c,b,a produces c→b→a→null. This takes O(n) time and O(n) reference storage. It is a valid identity-preserving baseline; allocating new nodes would violate this contract.

Improve the baseline

Carry just the frontier

The stack stores the whole order, but reversal can happen as each original edge is crossed. previous denotes the reversed prefix and current denotes the remaining original suffix.

Save before overwriting

First save next=current.next. Then set current.next=previous. Without the saved next, the only route to the suffix is destroyed.

Advance the two regions

Move previous=current and current=next. The old current is now the prefix head, and the saved original successor begins the remaining suffix. Return previous when current becomes null.

Why it is correct

Initialization

previous=null is the reversal of the empty prefix; current=head is the untouched input suffix.

Preservation

At each loop entry, the original nodes partition into a reversed prefix rooted at previous and an original-order suffix rooted at current. Saving next preserves access to the suffix. Redirecting one edge moves exactly one node from the suffix into the reversed prefix; no new object is introduced.

Termination

The suffix loses one node per iteration in a finite acyclic input. When it is empty, previous contains every original node in reverse order. The first redirected edge made the original head point to null, so the output terminates without a cycle.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

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

public final class Solution {
    public static final class Node {
        public final int value;
        public Node next;
        public Node(int value) { this.value = value; }
    }

    public static Node reverse(Node head) {
        Node previous = null;
        Node current = head;
        while (current != null) {
            Node next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }
        return previous;
    }

    public static Node baseline(Node head) {
        Deque<Node> stack = new ArrayDeque<>();
        for (Node node = head; node != null; node = node.next) stack.push(node);
        if (stack.isEmpty()) return null;
        Node result = stack.pop();
        Node tail = result;
        while (!stack.isEmpty()) {
            tail.next = stack.pop();
            tail = tail.next;
        }
        tail.next = null;
        return result;
    }
}

Read the meaningful blocks

Initialize boundaries

Two references represent the partition. Do not create a sentinel replacement list: the output must use original objects.

Save, redirect, advance

The order of these four assignments is the algorithm. next is the original successor, even after current.next changes.

Return the new head

current is null at termination. previous is the last processed node and therefore the new head.

Complexity

For n nodes, both methods perform O(n) work. Iterative reversal uses O(1) auxiliary references and allocates no nodes. Returned output reuses the input objects, so it is not O(n) newly allocated output.

The stack baseline uses O(n) auxiliary references. Recursive reversal also takes O(n) call-stack storage and may overflow the Java stack on deep lists; it is not a constant-space replacement.

Exact-state walkthroughs

Reveal normal and boundary traces

Three identities

Input: [1,2,3] · Result: "n2"

Step 1 of 11: Initialize reversed prefix and untouched suffix.

No node has moved; the reversed prefix is empty.

Node identities and current links

n0: 1
next → n1current
n1: 2
next → n2
n2: 3
next → null

Each card is an original node. “next” names its exact outgoing reference; cards remain in identity order as links change.

State after this step
Variable	Value
nodes	`[{"id":"n0","value":1,"next":"n1"},{"id":"n1","value":2,"next":"n2"},{"id":"n2","value":3,"next":null}]`
previous	`null`
current	`"n0"`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 import java.util.Deque;
 3 
 4 public final class Solution {
 5     public static final class Node {
 6         public final int value;
 7         public Node next;
 8         public Node(int value) { this.value = value; }
 9     }
10 
11     public static Node reverse(Node head) {
12         Node previous = null;
13         Node current = head;
14         while (current != null) {
15             Node next = current.next;
16             current.next = previous;
17             previous = current;
18             current = next;
19         }
20         return previous;
21     }
22 
23     public static Node baseline(Node head) {
24         Deque<Node> stack = new ArrayDeque<>();
25         for (Node node = head; node != null; node = node.next) stack.push(node);
26         if (stack.isEmpty()) return null;
27         Node result = stack.pop();
28         Node tail = result;
29         while (!stack.isEmpty()) {
30             tail.next = stack.pop();
31             tail = tail.next;
32         }
33         tail.next = null;
34         return result;
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize reversed prefix and untouched suffix.
No node has moved; the reversed prefix is empty.
nodes
[{"id":"n0","value":1,"next":"n1"},{"id":"n1","value":2,"next":"n2"},{"id":"n2","value":3,"next":null}]
previous
null
current
"n0"
Save the original successor of n0.
The suffix remains reachable after the link is overwritten.
nodes
[{"id":"n0","value":1,"next":"n1"},{"id":"n1","value":2,"next":"n2"},{"id":"n2","value":3,"next":null}]
previous
null
current
"n0"
savedNext
"n1"
Redirect n0.next to the reversed prefix.
The saved reference still protects the remaining suffix.
nodes
[{"id":"n0","value":1,"next":null},{"id":"n1","value":2,"next":"n2"},{"id":"n2","value":3,"next":null}]
previous
null
current
"n0"
savedNext
"n1"
Advance both region boundaries.
Reversed prefix and original suffix partition all original node identities.
nodes
[{"id":"n0","value":1,"next":null},{"id":"n1","value":2,"next":"n2"},{"id":"n2","value":3,"next":null}]
previous
"n0"
current
"n1"
Save the original successor of n1.
The suffix remains reachable after the link is overwritten.
nodes
[{"id":"n0","value":1,"next":null},{"id":"n1","value":2,"next":"n2"},{"id":"n2","value":3,"next":null}]
previous
"n0"
current
"n1"
savedNext
"n2"
Redirect n1.next to the reversed prefix.
The saved reference still protects the remaining suffix.
nodes
[{"id":"n0","value":1,"next":null},{"id":"n1","value":2,"next":"n0"},{"id":"n2","value":3,"next":null}]
previous
"n0"
current
"n1"
savedNext
"n2"
Advance both region boundaries.
Reversed prefix and original suffix partition all original node identities.
nodes
[{"id":"n0","value":1,"next":null},{"id":"n1","value":2,"next":"n0"},{"id":"n2","value":3,"next":null}]
previous
"n1"
current
"n2"
Save the original successor of n2.
The suffix remains reachable after the link is overwritten.
nodes
[{"id":"n0","value":1,"next":null},{"id":"n1","value":2,"next":"n0"},{"id":"n2","value":3,"next":null}]
previous
"n1"
current
"n2"
savedNext
null
Redirect n2.next to the reversed prefix.
The saved reference still protects the remaining suffix.
nodes
[{"id":"n0","value":1,"next":null},{"id":"n1","value":2,"next":"n0"},{"id":"n2","value":3,"next":"n1"}]
previous
"n1"
current
"n2"
savedNext
null
Advance both region boundaries.
Reversed prefix and original suffix partition all original node identities.
nodes
[{"id":"n0","value":1,"next":null},{"id":"n1","value":2,"next":"n0"},{"id":"n2","value":3,"next":"n1"}]
previous
"n2"
current
null
Return the contract result.
The result follows from the completed state and the declared contract.
result
"n2"

Empty list

Input: [] · Result: null

Step 1 of 2: Initialize reversed prefix and untouched suffix.

No node has moved; the reversed prefix is empty.

Node identities and current links

Each card is an original node. “next” names its exact outgoing reference; cards remain in identity order as links change.

State after this step
Variable	Value
nodes	`[]`
previous	`null`
current	`null`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 import java.util.Deque;
 3 
 4 public final class Solution {
 5     public static final class Node {
 6         public final int value;
 7         public Node next;
 8         public Node(int value) { this.value = value; }
 9     }
10 
11     public static Node reverse(Node head) {
12         Node previous = null;
13         Node current = head;
14         while (current != null) {
15             Node next = current.next;
16             current.next = previous;
17             previous = current;
18             current = next;
19         }
20         return previous;
21     }
22 
23     public static Node baseline(Node head) {
24         Deque<Node> stack = new ArrayDeque<>();
25         for (Node node = head; node != null; node = node.next) stack.push(node);
26         if (stack.isEmpty()) return null;
27         Node result = stack.pop();
28         Node tail = result;
29         while (!stack.isEmpty()) {
30             tail.next = stack.pop();
31             tail = tail.next;
32         }
33         tail.next = null;
34         return result;
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize reversed prefix and untouched suffix.
No node has moved; the reversed prefix is empty.
nodes
[]
previous
null
current
null
Return the contract result.
The result follows from the completed state and the declared contract.
result
null

Test the contract

Input: null
Output: null
Empty input.
Input: a(9) → null
Output: a(9) → null
Same head identity.
Input: a(1) → b(2) → null
Output: b(2) → a(1) → null
Smallest changed list.
Input: a(5) → b(5) → c(5)
Output: c(5) → b(5) → a(5)
All equal values expose identity bugs.

Common mistakes and counterexamples

Overwrite next before saving the suffix

Counterexample: a→b→null; setting a.next=null before remembering b loses b.

Save current.next into next first.

Move current through the changed link

Counterexample: After current.next=previous, current=current.next walks backward.

Advance through the saved next, not the overwritten field.

Return the original head

Counterexample: a→b returns a→null, losing b from the output.

Return previous, which is the old tail.

Validate only reversed values

Counterexample: a(5)→b(5) can be copied or left unchanged and still look correct.

Compare reference identity order and ensure oldHead.next=null and no cycle.

Follow-ups

Reverse only positions left through right.

Keep the node before the segment and the segment tail; reverse the bounded region and reconnect both boundaries. Test segments touching the head/tail. Off-by-one and lost suffix links become the main risks.

Determine whether the input is a palindrome without changing its final structure.

Find the midpoint, reverse one half, compare, and restore that half even when a mismatch is found. Tests must check original references and links after return.

What changes if cycles are possible?

This contract no longer applies. Decide whether to reject a cycle or define another operation; Floyd cycle detection can validate in O(n) time and O(1) extra space before mutation.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 104/20,000 characters

Self-review

I can name the two disjoint regions at each loop entry.I saved the original successor before overwriting the link.I checked identities, termination, and reverse-twice restoration.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Linked lists: identity, reachability, and update order

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-14 · Original teaching content and implementations authored for AceYourInterviews. Familiar interview problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.