DSA-053 · Dummy predecessor and fixed pointer gap

Remove Nth Node from End

Core · Java 21 · Version 1 · editorial draft

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

Understand the problem

Remove the nth node counted from the end of an acyclic singly linked list. Return the new head, reusing every surviving node. Detach the removed node by setting its next field to null.

head is null or a finite acyclic list with at most 100,000 distinct nodes. Values are arbitrary final ints, and next links are mutable. Cycles and concurrent structural changes are outside the contract.
n is a one-based position from the end. If n<=0 or n exceeds the length, throw IllegalArgumentException before changing any original link. Thus every n is invalid for an empty list.
On success, retain survivor identities, values, and relative order. Set removed.next=null, including when the removed node was the head. Return null when removing the sole node. Aliases to the predecessor and removed node observe these writes; destructive ownership permission is required.

Examples

Input: N0(1)→N1(2)→N2(3)→N3(4)→N4(5), n=2
Output: N0→N1→N2→N4; N3.next=null
N3 is second from the end. Splice through its predecessor N2 and detach N3.
Input: N0→N1, n=2
Output: N1; N0.next=null
The dummy acts as the predecessor of the original head. The caller must use the returned head.
Input: N0→N1, n=3
Output: IllegalArgumentException; original N0.next=N1
The setup cursor exhausts before establishing its gap, so no splice occurs.

Before you start

Singly linked node identity and destructive splicing
Null guards and a dummy predecessor

Recognize the structure

A position from the end cannot be recognized locally before the suffix is known. Either count length, or retain a fixed offset between two references. A dummy predecessor unifies head removal with interior removal. This is deletion by relative position, not deletion by value.

Try before revealing

Hint 1

What would the predecessor index be if the length were known?

Hint 2

A dummy predecessor allows head removal to use the ordinary splice.

Hint 3

Advance fast n edges from dummy, walk both until fast is the tail, then bypass slow.next and detach it.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Count length, then find the predecessor

Count L nodes without writing. Validate 1<=n<=L, then move L−n edges from dummy to the predecessor, splice its successor out, and detach the removed node. For L=5,n=2, move three edges from dummy to N2, then bypass N3. This takes O(L) time and O(1) space, with two traversals of part or all of the list. The gap method avoids a separate length-counting pass but has the same asymptotic cost.

Improve the baseline

Establish exactly n edges

Start fast at dummy and advance n edges, checking fast.next before each move. No original field changes during validation. If there are too few nodes, throw immediately.

Keep the gap until fast is the tail

Start slow at dummy after setup. Advance both while fast.next!=null, preserving an n-edge gap. When fast is the last node, slow is exactly the predecessor of the nth node from the end.

Splice and detach deliberately

Save removed=slow.next; set slow.next=removed.next, then removed.next=null. Returning dummy.next handles the changed-head case. Detachment is a separate observable contract choice, not an incidental implementation detail.

Why it is correct

Valid setup and failure atomicity

After i setup moves, fast is i edges after dummy. The next move exists precisely when another input node is available. For n>L the check throws before any original write; n<=0 is rejected even earlier.

Fixed-gap invariant

During the joint walk, fast remains n edges ahead of slow. Label dummy position −1 and input positions 0..L−1. When fast reaches position L−1, slow is at L−1−n, so its successor has index L−n, the required deletion target.

Identity-preserving result

Bypassing one node changes only the predecessor edge, or the private dummy edge for head deletion. Detaching the removed object cannot affect the remaining chain because no survivor points to it. All other links and all values remain unchanged, and the output remains acyclic.

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.


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 removeNth(Node head, int n) {
        if (n <= 0) throw new IllegalArgumentException("n must be positive");
        Node dummy = new Node(0);
        dummy.next = head;
        Node fast = dummy;
        for (int i = 0; i < n; i++) {
            if (fast.next == null) throw new IllegalArgumentException("n exceeds length");
            fast = fast.next;
        }
        Node slow = dummy;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        Node removed = slow.next;
        slow.next = removed.next;
        removed.next = null;
        return dummy.next;
    }

    public static Node baseline(Node head, int n) {
        int length = 0;
        for (Node p = head; p != null; p = p.next) length++;
        if (n <= 0 || n > length) throw new IllegalArgumentException("invalid n");
        Node dummy = new Node(0);
        dummy.next = head;
        Node previous = dummy;
        for (int i = 0; i < length - n; i++) previous = previous.next;
        Node removed = previous.next;
        previous.next = removed.next;
        removed.next = null;
        return dummy.next;
    }
}

Read the meaningful blocks

Validate before mutation

The guarded n-step setup rejects a bad request without partially editing the caller’s list. n=Integer.MAX_VALUE still fails after the finite input exhausts.

Stop at fast.next==null

This implementation uses n edges and stops fast at the tail. Mixing it with the alternative n+1-gap/fast==null convention causes an off-by-one splice.

Detach after bypassing

Clearing removed.next first would lose the successor unless it had been saved. The implementation bypasses first and then clears the detached node.

Complexity

Both methods take O(L) worst-case time and O(1) auxiliary space; a private dummy is constant allocation and never belongs to the returned list. The optimized method maintains a gap instead of first counting the whole length.

In the optimized method, invalid n>L is rejected in O(L) work with no original mutation, while n<=0 rejects in O(1). The length-counting baseline traverses before rejecting. Surviving nodes are reused, so there is no linear output allocation.

Exact-state walkthroughs

Reveal normal and boundary traces

Remove the second node from the end

Input: {"values":[1,2,3,4,5],"n":2} · Outcome / chain identities: ["N0","N1","N2","N4"]

Step 1 of 9: Start the n-edge setup without writing an original field.

dummy is a private predecessor; fast has advanced zero edges.

Deletion — predecessor gap and surviving identities

Phase: initial. fast: dummy · slow: dummy

Requested n: 2. Setup gap: 0. Private dummy.next: N0. Removed: (not selected).

N0: 1next → N1
N1: 2next → N2
N2: 3next → N3
N3: 4next → N4
N4: 5next → null

Cards remain in identity order; follow the named links for traversal order. The dummy is a private predecessor, outside the node cards and returned output.

State after this step
Variable	Value
nodes	`[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":"N4"},{"id":"N4","value":5,"next":null}]`
pointers	`{"fast":"dummy","slow":"dummy"}`
dummyNext	`"N0"`
gap	`0`
n	`2`
removed	`null`
phase	`"initial"`

See the affected Java block

 1 
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node next;
 6         public Node(int value) { this.value = value; }
 7     }
 8 
 9     public static Node removeNth(Node head, int n) {
10         if (n <= 0) throw new IllegalArgumentException("n must be positive");
11         Node dummy = new Node(0);
12         dummy.next = head;
13         Node fast = dummy;
14         for (int i = 0; i < n; i++) {
15             if (fast.next == null) throw new IllegalArgumentException("n exceeds length");
16             fast = fast.next;
17         }
18         Node slow = dummy;
19         while (fast.next != null) {
20             fast = fast.next;
21             slow = slow.next;
22         }
23         Node removed = slow.next;
24         slow.next = removed.next;
25         removed.next = null;
26         return dummy.next;
27     }
28 
29     public static Node baseline(Node head, int n) {
30         int length = 0;
31         for (Node p = head; p != null; p = p.next) length++;
32         if (n <= 0 || n > length) throw new IllegalArgumentException("invalid n");
33         Node dummy = new Node(0);
34         dummy.next = head;
35         Node previous = dummy;
36         for (int i = 0; i < length - n; i++) previous = previous.next;
37         Node removed = previous.next;
38         previous.next = removed.next;
39         removed.next = null;
40         return dummy.next;
41     }
42 }
43

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

Read the full static trace

Start the n-edge setup without writing an original field.
dummy is a private predecessor; fast has advanced zero edges.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":"N4"},{"id":"N4","value":5,"next":null}]
pointers
{"fast":"dummy","slow":"dummy"}
dummyNext
"N0"
gap
0
n
2
removed
null
phase
"initial"
Advance fast one setup edge.
fast is gap edges after dummy; no original fields have been written.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":"N4"},{"id":"N4","value":5,"next":null}]
pointers
{"fast":"N0","slow":"dummy"}
dummyNext
"N0"
gap
1
n
2
removed
null
phase
"gap"
Advance fast one setup edge.
fast is gap edges after dummy; no original fields have been written.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":"N4"},{"id":"N4","value":5,"next":null}]
pointers
{"fast":"N1","slow":"dummy"}
dummyNext
"N0"
gap
2
n
2
removed
null
phase
"gap"
Advance both while retaining exactly n edges.
When fast reaches the tail, slow is the required predecessor.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":"N4"},{"id":"N4","value":5,"next":null}]
pointers
{"fast":"N2","slow":"N0"}
dummyNext
"N0"
gap
2
n
2
removed
null
phase
"walk"
Advance both while retaining exactly n edges.
When fast reaches the tail, slow is the required predecessor.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":"N4"},{"id":"N4","value":5,"next":null}]
pointers
{"fast":"N3","slow":"N1"}
dummyNext
"N0"
gap
2
n
2
removed
null
phase
"walk"
Advance both while retaining exactly n edges.
When fast reaches the tail, slow is the required predecessor.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":"N4"},{"id":"N4","value":5,"next":null}]
pointers
{"fast":"N4","slow":"N2"}
dummyNext
"N0"
gap
2
n
2
removed
null
phase
"walk"
Bypass the exact target identity.
Survivors remain reachable; the removed object still points to its old successor until the next statement.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N4"},{"id":"N3","value":4,"next":"N4"},{"id":"N4","value":5,"next":null}]
pointers
{"fast":"N4","slow":"N2"}
dummyNext
"N0"
gap
2
n
2
removed
"N3"
phase
"splice"
Detach the removed object explicitly.
The removed node cannot traverse into survivors. All survivor identities and values are preserved.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N4"},{"id":"N3","value":4,"next":null},{"id":"N4","value":5,"next":null}]
pointers
{"fast":"N4","slow":"N2"}
dummyNext
"N0"
gap
2
n
2
removed
"N3"
phase
"detach"
Return the documented outcome after all required mutation or restoration.
An array here is an ordered identity view of the Java head-reference result; an error record denotes the declared exception.
result
["N0","N1","N2","N4"]

Remove the head through the dummy

Input: {"values":[7,7],"n":2} · Outcome / chain identities: ["N1"]

Step 1 of 6: Start the n-edge setup without writing an original field.

dummy is a private predecessor; fast has advanced zero edges.

Deletion — predecessor gap and surviving identities

Phase: initial. fast: dummy · slow: dummy

Requested n: 2. Setup gap: 0. Private dummy.next: N0. Removed: (not selected).

N0: 7next → N1
N1: 7next → null

Cards remain in identity order; follow the named links for traversal order. The dummy is a private predecessor, outside the node cards and returned output.

State after this step
Variable	Value
nodes	`[{"id":"N0","value":7,"next":"N1"},{"id":"N1","value":7,"next":null}]`
pointers	`{"fast":"dummy","slow":"dummy"}`
dummyNext	`"N0"`
gap	`0`
n	`2`
removed	`null`
phase	`"initial"`

See the affected Java block

 1 
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node next;
 6         public Node(int value) { this.value = value; }
 7     }
 8 
 9     public static Node removeNth(Node head, int n) {
10         if (n <= 0) throw new IllegalArgumentException("n must be positive");
11         Node dummy = new Node(0);
12         dummy.next = head;
13         Node fast = dummy;
14         for (int i = 0; i < n; i++) {
15             if (fast.next == null) throw new IllegalArgumentException("n exceeds length");
16             fast = fast.next;
17         }
18         Node slow = dummy;
19         while (fast.next != null) {
20             fast = fast.next;
21             slow = slow.next;
22         }
23         Node removed = slow.next;
24         slow.next = removed.next;
25         removed.next = null;
26         return dummy.next;
27     }
28 
29     public static Node baseline(Node head, int n) {
30         int length = 0;
31         for (Node p = head; p != null; p = p.next) length++;
32         if (n <= 0 || n > length) throw new IllegalArgumentException("invalid n");
33         Node dummy = new Node(0);
34         dummy.next = head;
35         Node previous = dummy;
36         for (int i = 0; i < length - n; i++) previous = previous.next;
37         Node removed = previous.next;
38         previous.next = removed.next;
39         removed.next = null;
40         return dummy.next;
41     }
42 }
43

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

Read the full static trace

Start the n-edge setup without writing an original field.
dummy is a private predecessor; fast has advanced zero edges.
nodes
[{"id":"N0","value":7,"next":"N1"},{"id":"N1","value":7,"next":null}]
pointers
{"fast":"dummy","slow":"dummy"}
dummyNext
"N0"
gap
0
n
2
removed
null
phase
"initial"
Advance fast one setup edge.
fast is gap edges after dummy; no original fields have been written.
nodes
[{"id":"N0","value":7,"next":"N1"},{"id":"N1","value":7,"next":null}]
pointers
{"fast":"N0","slow":"dummy"}
dummyNext
"N0"
gap
1
n
2
removed
null
phase
"gap"
Advance fast one setup edge.
fast is gap edges after dummy; no original fields have been written.
nodes
[{"id":"N0","value":7,"next":"N1"},{"id":"N1","value":7,"next":null}]
pointers
{"fast":"N1","slow":"dummy"}
dummyNext
"N0"
gap
2
n
2
removed
null
phase
"gap"
Bypass the exact target identity.
Survivors remain reachable; the removed object still points to its old successor until the next statement.
nodes
[{"id":"N0","value":7,"next":"N1"},{"id":"N1","value":7,"next":null}]
pointers
{"fast":"N1","slow":"dummy"}
dummyNext
"N1"
gap
2
n
2
removed
"N0"
phase
"splice"
Detach the removed object explicitly.
The removed node cannot traverse into survivors. All survivor identities and values are preserved.
nodes
[{"id":"N0","value":7,"next":null},{"id":"N1","value":7,"next":null}]
pointers
{"fast":"N1","slow":"dummy"}
dummyNext
"N1"
gap
2
n
2
removed
"N0"
phase
"detach"
Return the documented outcome after all required mutation or restoration.
An array here is an ordered identity view of the Java head-reference result; an error record denotes the declared exception.
result
["N1"]

Reject an oversized position before mutation

Input: {"values":[1,2],"n":3} · Outcome / chain identities: {"error":"IllegalArgumentException"}

Step 1 of 5: Start the n-edge setup without writing an original field.

dummy is a private predecessor; fast has advanced zero edges.

Deletion — predecessor gap and surviving identities

Phase: initial. fast: dummy · slow: dummy

Requested n: 3. Setup gap: 0. Private dummy.next: N0. Removed: (not selected).

N0: 1next → N1
N1: 2next → null

Cards remain in identity order; follow the named links for traversal order. The dummy is a private predecessor, outside the node cards and returned output.

State after this step
Variable	Value
nodes	`[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":null}]`
pointers	`{"fast":"dummy","slow":"dummy"}`
dummyNext	`"N0"`
gap	`0`
n	`3`
removed	`null`
phase	`"initial"`

See the affected Java block

 1 
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node next;
 6         public Node(int value) { this.value = value; }
 7     }
 8 
 9     public static Node removeNth(Node head, int n) {
10         if (n <= 0) throw new IllegalArgumentException("n must be positive");
11         Node dummy = new Node(0);
12         dummy.next = head;
13         Node fast = dummy;
14         for (int i = 0; i < n; i++) {
15             if (fast.next == null) throw new IllegalArgumentException("n exceeds length");
16             fast = fast.next;
17         }
18         Node slow = dummy;
19         while (fast.next != null) {
20             fast = fast.next;
21             slow = slow.next;
22         }
23         Node removed = slow.next;
24         slow.next = removed.next;
25         removed.next = null;
26         return dummy.next;
27     }
28 
29     public static Node baseline(Node head, int n) {
30         int length = 0;
31         for (Node p = head; p != null; p = p.next) length++;
32         if (n <= 0 || n > length) throw new IllegalArgumentException("invalid n");
33         Node dummy = new Node(0);
34         dummy.next = head;
35         Node previous = dummy;
36         for (int i = 0; i < length - n; i++) previous = previous.next;
37         Node removed = previous.next;
38         previous.next = removed.next;
39         removed.next = null;
40         return dummy.next;
41     }
42 }
43

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

Read the full static trace

Start the n-edge setup without writing an original field.
dummy is a private predecessor; fast has advanced zero edges.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":null}]
pointers
{"fast":"dummy","slow":"dummy"}
dummyNext
"N0"
gap
0
n
3
removed
null
phase
"initial"
Advance fast one setup edge.
fast is gap edges after dummy; no original fields have been written.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":null}]
pointers
{"fast":"N0","slow":"dummy"}
dummyNext
"N0"
gap
1
n
3
removed
null
phase
"gap"
Advance fast one setup edge.
fast is gap edges after dummy; no original fields have been written.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":null}]
pointers
{"fast":"N1","slow":"dummy"}
dummyNext
"N0"
gap
2
n
3
removed
null
phase
"gap"
The full gap cannot be established; reject before any splice.
Invalid n leaves the entire original graph unchanged.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":null}]
pointers
{"fast":"N1","slow":"dummy"}
dummyNext
"N0"
gap
2
n
3
removed
null
phase
"invalid"
Report the declared exception with the original graph unchanged.
An array here is an ordered identity view of the Java head-reference result; an error record denotes the declared exception.
result
{"error":"IllegalArgumentException"}

Test the contract

Input: null,n=1
Output: IllegalArgumentException
Every empty-list request is invalid and leaves the graph untouched.
Input: N0,n=1
Output: null; N0.next=null
Singleton.
Input: N0→N1→N2,n=3
Output: N1→N2; N0.next=null
Remove head.
Input: N0→N1→N2,n=1
Output: N0→N1; N2 detached
Remove tail.
Input: Two nodes,n=0 or 3
Output: IllegalArgumentException; unchanged edges
Bad positions must not mutate.

Common mistakes and counterexamples

Mix two gap conventions

Counterexample: With two nodes and n=1, moving fast n+1 steps but stopping at the tail skips the correct predecessor.

State the exact invariant: n edges from slow to fast, stop when fast.next is null.

Remove by matching a value

Counterexample: Three nodes valued 7 still have distinct positions and identities.

Compute the position and test the returned reference sequence.

Detach before saving the successor

Counterexample: Clearing removed.next before bypassing can truncate the whole suffix.

Assign predecessor.next=removed.next first, then clear removed.next.

Mutate during incomplete validation

Counterexample: n greater than length could leave a partially edited list before an exception.

Establish the entire gap before any original write and assert every link on invalid cases.

Follow-ups

Return the removed object too.

Return a record containing the new head and removed node. Preserve the detached-next contract so its ownership and traversal semantics are explicit.

Can a forward-only stream solve this without retained references?

A stream cannot delete an already emitted occurrence after discovering its distance from the end. Delayed output needs an n-sized buffer; mutable linked nodes permit retaining the predecessor and editing it once the tail is known.

What changes for an immutable list?

Rebuild the prefix before the removed position and share the untouched suffix only if immutability permits it. This uses O(L) new nodes in the worst case and changes the identity contract.

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 · 126/20,000 characters

Self-review

I can name my gap and stop condition without switching conventions.I test invalid requests for unchanged original edges.I verify the exact removed identity is detached and every survivor remains in order.

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-16 · Original teaching content and implementations authored for AceYourInterviews. Standard problem names do not imply company-frequency or external platform-difficulty claims.