Reverse a singly linked chain in Java without allocating new nodes

Keep three references alive

A node exposes only its successor. Save that successor before changing the link; otherwise the unvisited suffix becomes unreachable from the current traversal. At each step, current.next points to the already reversed prefix, and previous advances to current. When current becomes null, previous is the new head.

This is an algorithm for an application-owned Node chain. java.util.LinkedList does not expose its internal nodes. To inspect that collection backward, use descendingIterator or a reversed view where supported; rebuilding a list by repeated indexed access would pay for repeated link walks.

State the precondition

The input must be acyclic. A cycle would prevent the loop from reaching null and would mutate the cycle while it ran. If the chain comes from untrusted graph construction, run cycle detection first. The method also works for null and a single node, which makes those useful boundary fixtures.

Reversal changes the caller's chain. Any old head reference now identifies the tail. If another owner still uses the old head as though it represented the whole sequence, it sees a truncated path; return and publish the new head as one ownership change.

Working program

public class ReverseDispatchChain {
    static final class Node {
        final String dispatchId;
        Node next;
        Node(String dispatchId, Node next) { this.dispatchId = dispatchId; this.next = next; }
    }
    static Node reverse(Node head) {
        Node previous = null;
        Node current = head;
        while (current != null) {
            Node following = current.next;
            current.next = previous;
            previous = current;
            current = following;
        }
        return previous;
    }
    static String labels(Node head) {
        StringBuilder result = new StringBuilder();
        for (Node current = head; current != null; current = current.next) {
            if (result.length() > 0) result.append(",");
            result.append(current.dispatchId);
        }
        return result.toString();
    }
    public static void main(String[] args) {
        Node head = new Node("load-47", new Node("seal-82", new Node("ship-15", null)));
        System.out.println(labels(reverse(head)));
        System.out.println(reverse(null) == null);
    }
}

Output

ship-15,seal-82,load-47
true

Cost and ownership

One pass visits n nodes in O(n) time and holds O(1) extra node references. It does not copy payload objects. The method is not safe to run while another thread traverses or mutates the same chain without an ownership or synchronization boundary.

Common Mistakes

• Do not overwrite current.next before saving the next unvisited node.
• Do not keep using the old head as the root after reversal.
• Do not run a null-terminated loop on a chain that may contain a cycle.

Read next

linked cycle entry, linked palindrome restore, Java LinkedList: operations, internals and failure cases, Java LinkedList descendingIterator: inspect and remove from the tail.

Continue with owned-node algorithms

Continue with Reverse complete groups of k nodes in a Java linked chain, Test Java linked-chain mutations with node-identity invariants.