Reverse a Singly Linked List

Reversing a singly linked list is four lines inside a loop, and the four lines have exactly one valid order. Overwriting current.next before saving it disconnects everything after the current node, and the list is gone. There is no way back, because the only reference to the remainder was the pointer just overwritten.

Written against Java 17.

The node

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) { this.val = val; }
}

1 -> 2 -> 3 -> 4 -> null
becomes
4 -> 3 -> 2 -> 1 -> null

The iterative solution

static ListNode reverse(ListNode head) {
    ListNode previous = null;
    ListNode current = head;

    while (current != null) {
        ListNode next = current.next;   // 1. save what comes after
        current.next = previous;        // 2. flip this link
        previous = current;             // 3. advance previous
        current = next;                 // 4. advance current
    }
    return previous;                    // the old tail is the new head
}

O(n) time, O(1) space. Three pointers and one pass.

Why the order cannot change

Step 1 must come before step 2. current.next = previous overwrites the only reference to the rest of the list; without next holding it first, everything from there on is unreachable and, in Java, garbage.

Steps 3 and 4 must come after step 2 and in that order. Assigning current = next before previous = current loses the node just processed, so the next iteration links to the wrong place.

A useful way to hold it: save, flip, advance, advance. Every incorrect ordering either drops the tail or drops the node just finished.

Returning previous, not current

At the end of the loop current is null. That is why the loop stopped. previous points at the last node processed, which was the original tail and is now the head.

Returning current returns null, and the caller sees an empty list. It compiles, and it is the second most common mistake here.

The original head is now the tail, and its next is null: set on the first iteration, when previous was still null. That initialisation is what terminates the reversed list correctly, and it is why previous starts at null rather than at head.

Tracing it

Starting from 1 -> 2 -> 3 -> null:

step	previous	current	next	list so far
initial	null	1	—	1 -> 2 -> 3
after 1	1	2	2	1 -> null, 2 -> 3
after 2	2	3	3	2 -> 1 -> null, 3
after 3	3	null	null	3 -> 2 -> 1 -> null

The list is momentarily in two pieces during each iteration, which is normal — previous holds the reversed prefix and current holds the untouched remainder.

The recursive solution

static ListNode reverseRecursive(ListNode head) {
    if (head == null || head.next == null) {
        return head;                    // base case: empty or single node
    }

    ListNode newHead = reverseRecursive(head.next);   // reverse the rest first

    head.next.next = head;              // make the next node point back at us
    head.next = null;                   // and break the forward link

    return newHead;                     // the same head all the way up
}

The recursion descends to the last node, which becomes the new head and is returned unchanged through every frame. The reversal happens on the way back up.

head.next.next = head is the line worth reading twice. At that point head.next is still the original next node — the recursive call reversed everything beyond it but did not touch this link — so head.next.next is that node’s forward pointer, and setting it to head reverses this one link.

head.next = null then breaks the old forward link. Omitting it leaves a two-node cycle between the last pair, and any traversal afterwards loops forever.

The base case tests both head == null (empty list) and head.next == null (single node). Dropping the first throws on an empty input; dropping the second recurses into null.

Which to use

The recursion is O(n) time and O(n) space for the call stack. On a list of a million nodes that is a StackOverflowError, and the JVM does not eliminate the call because it is not in tail position — the work happens after the recursive call returns.

The iterative version is O(1) space and has no depth limit. Use it, the recursive form is worth writing once to understand the structure, and it is the natural shape in a language with proper tail calls, which Java is not.

Reversing part of a list

The same three-pointer move, applied to a sublist, is the version that appears in real problems:

static ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode sentinel = new ListNode(0);
    sentinel.next = head;

    ListNode beforeLeft = sentinel;
    for (int i = 1; i < left; i++) {
        beforeLeft = beforeLeft.next;
    }

    ListNode tail = beforeLeft.next;    // will end up as the LAST node of the reversed part

    for (int i = 0; i < right - left; i++) {
        ListNode moved = tail.next;
        tail.next = moved.next;
        moved.next = beforeLeft.next;
        beforeLeft.next = moved;
    }
    return sentinel.next;
}

The sentinel node is what removes the special case. Without it, reversing from position 1 changes the head, and every line has to handle that separately. With it, there is always a node before the region being modified, and sentinel.next is the answer at the end.

That trick generalises: any linked-list operation that can affect the head is simpler with a sentinel, and the cost is one allocation.

Testing it

The failure modes are all structural, so an assertion on the values alone is not enough — a list with a cycle can still yield the right first few values.

static List<Integer> toList(ListNode head) {
    List<Integer> out = new ArrayList<>();
    int guard = 0;
    for (ListNode n = head; n != null; n = n.next) {
        if (++guard > 10_000) throw new IllegalStateException("cycle detected");
        out.add(n.val);
    }
    return out;
}

The guard turns an infinite traversal into a failing test rather than a hanging one, which matters because the recursive version’s missing head.next = null produces exactly that.

Then check every length from 0 to a few:

for (int n = 0; n <= 5; n++) {
    ListNode head = build(IntStream.range(0, n).toArray());
    List<Integer> expected = new ArrayList<>(toList(head));
    Collections.reverse(expected);
    assertEquals(expected, toList(reverse(head)));
}

Lengths 0, 1 and 2 catch every ordering mistake in the loop. A test that starts at length 5 catches most of them and misses the null-head case entirely.

Edge cases

• Empty list — head is null, the loop does not run, previous is null, and null is returned. Correct with no guard.
• Single node — one iteration, next is null, the node points at null, and it is returned.
• Two nodes — the minimum case where the ordering can go wrong; worth an explicit test.
• A cycle — the loop never terminates. Reversing a cyclic list is undefined; detect cycles with Floyd’s algorithm first if the input is untrusted.

Why this problem keeps appearing

It is the smallest problem that requires holding three simultaneous references and reasoning about an order of assignments. That skill is what the rest of the linked-list family needs: reordering a list, merging two, detecting a palindrome by reversing the second half, reversing in groups of k.

It also has no clever insight — the solution is the obvious one, correctly ordered — which makes it a test of care rather than of invention.

The pointer discipline here is also what an LRU cache needs — its doubly linked list unlinks and relinks a node on every access, and the sentinels it uses exist to remove exactly the null cases this problem makes you handle by hand. For the LIFO structure itself, see Java Stack. More in the algorithms guides.

Frequently asked questions

Why must next be saved before flipping the link?

current.next = previous overwrites the only reference to the rest of the list. Without saving it first, everything after the current node is unreachable.

Why return previous instead of current?

The loop ends when current is null. previous holds the last node processed, which is the new head.

Why does previous start as null?

So the original head’s next becomes null on the first iteration, correctly terminating the reversed list.

What is the space complexity?

O(1) for the iterative version, the recursive one is O(n) for the call stack.

Will the recursive version overflow the stack?

On a long enough list, yes. The call is not in tail position — the work happens after it returns — so the JVM cannot eliminate it.

What does head.next.next = head do?

It makes the following node point back at the current one. At that moment head.next is still the original successor, so its forward pointer is what gets reversed.

Why set head.next = null in the recursive version?

Otherwise the last two nodes point at each other and any traversal loops forever.

Do I need a special case for an empty list?

No, the loop does not run and null is returned, which is correct.

How do I reverse only part of a list?

Use a sentinel node before the head so the case where the head itself moves needs no special handling, then repeatedly move the node after the region’s start to its front.

What happens if the list has a cycle?

The loop never terminates. Detect cycles first with a slow-fast pointer if the input cannot be trusted.