Remove the nth node from the end of a Java linked chain

Last updated: 1 Oct 20264 min read

tutorial

Removing the nth node from the end requires a gap of n links between two cursors, then one link replacement at the predecessor.

Reject an invalid position before mutation

Use a sentinel before the head so deletion of the first real node follows the same rule as deletion in the middle. Advance the leading cursor n links from the sentinel. If it reaches null too early, n exceeds the chain length. Zero and negative positions are not meaningful and must fail before any link changes.

Keep the cursor gap fixed while the leading cursor still has a successor. The trailing cursor then stops at the predecessor of the target. Save the target, bypass it, and clear its next reference so code that still holds the removed node cannot walk into the live chain.

State the ownership boundary

This operation mutates an application-owned acyclic Node chain. It is not a way to obtain internal nodes from java.util.LinkedList. If a caller retains aliases into the original chain, those aliases still point to the same objects; only the root and predecessor links change. Run cycle detection first if the input can contain a cycle.

A successful deletion returns the possibly new head. Ignoring that return value loses a head deletion. For value-based removal through the collection API, use LinkedList occurrence removal instead.

Working program

public class RemoveDispatchFromTail {
    static final class Node {
        final String dispatchId;
        Node next;
        Node(String dispatchId, Node next) { this.dispatchId = dispatchId; this.next = next; }
    }
    static Node remove(Node head, int positionFromEnd) {
        if (positionFromEnd <= 0) throw new IllegalArgumentException("position must be positive");
        Node sentinel = new Node("sentinel", head);
        Node lead = sentinel;
        for (int step = 0; step < positionFromEnd; step++) {
            if (lead.next == null) throw new IllegalArgumentException("position exceeds length");
            lead = lead.next;
        }
        Node before = sentinel;
        while (lead.next != null) { lead = lead.next; before = before.next; }
        Node removed = before.next;
        before.next = removed.next;
        removed.next = null;
        return sentinel.next;
    }
    static String labels(Node head) {
        StringBuilder result = new StringBuilder();
        for (Node cursor = head; cursor != null; cursor = cursor.next) {
            if (result.length() > 0) result.append(",");
            result.append(cursor.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)));
        head = remove(head, 3);
        System.out.println(labels(head));
        head = remove(head, 1);
        System.out.println(labels(head));
        try { remove(head, 2); }
        catch (IllegalArgumentException rejected) { System.out.println("invalid position rejected"); }
    }
}

Output

seal-82,ship-15
seal-82
invalid position rejected

Cost and ownership

One traversal takes O(n) time and O(1) extra references. The sentinel is one temporary node allocation. This method assumes exclusive mutation of the chain; concurrent readers need a separate publication or synchronization rule.

Common Mistakes

Do not treat n as a zero-based offset.
Do not ignore the returned head when the first node can be removed.
Do not advance both cursors before checking whether the requested position exists.