Difficulty: MediumLinked List

Remove Nth Node From End of List

Problem in Plain English

Given the head of a singly linked list and an integer n, remove the nth node from the end of the list in a single pass and return the head of the modified list.

Problem Statement

Given the head of a singly linked list, remove the nth node from the end of the list and return the head of the modified list.

The position n is always valid, and the follow-up asks for a single-pass solution.

Reuse the surviving nodes in their original order and change only the link needed to bypass the target. The removed node need not have its own next link cleared; it simply must be unreachable from the returned head.

Constraints

The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

Examples

Example 1

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

The 2nd node from the end holds 4, so removing it leaves [1,2,3,5].

Example 2

Input: head = [1], n = 1
Output: []

Removing the only node leaves an empty list.

Example 3

Input: head = [1,2], n = 1
Output: [1]

The 1st node from the end holds 2, so removing it leaves [1].

Example 4

Input: head = [7,7,7], n = 3
Output: [7,7]

The 3rd node from the end is the original head even though all values are equal. Return the original second node, retaining the other two nodes in order; values alone cannot identify which node was removed.

Intuition

A singly linked list cannot walk backward, so locate the target's predecessor using information gathered while moving forward. If the length is L, the target has one-based position L - n + 1; in Example 1 that is position 4, holding value 4. Either measure L first, or keep a leader n + 1 links ahead of a trailer so the leader reaching null places the trailer immediately before the target. A dummy predecessor makes removing the head work like any other deletion.

Approaches

Two Passes

Solution Details

Reveal Two Passes: intuition, complexity, and code

Intuition

Count the total length L to translate the end-relative position n into a forward index L - n. For Example 1, L = 5 and n = 2 give target index 3, so its predecessor is index 2, the node with value 3. Deleting index 0 needs a new head; all other deletions need just one next-link update.

Step-by-Step Logic

Traverse the whole list and count L; Example 1 visits 1, 2, 3, 4 and 5, reaching length = 5.
Compute the target index length - n; Example 1 gives 5 - 2 = 3. If the index is zero, return the original head.next.
Otherwise advance curr from head to the node just before that index. Example 1 moves from node 1 to node 2 to node 3, the predecessor of node 4.
Bypass exactly one node with curr.next = curr.next.next; Example 1 changes the link from 3 → 4 into 3 → 5. Return head, yielding [1,2,3,5].

Why It Works

The first traversal counts every node once, so length equals L. The nth node from the end has zero-based index L - n. If this index is zero, returning head.next omits exactly the original head and preserves the remaining suffix. Otherwise, curr starts at index zero and advances L - n - 1 times, ending at the predecessor index L - n - 1. Assigning curr.next to curr.next.next omits exactly the target while preserving all other node identities, values and order. Valid n guarantees the target exists. No link points backward, so the resulting chain remains acyclic.

Dry Run

Two Passes: variable states at each step
Event	curr after event	length	Seek loop i	Next link or result
Initialize count	node 1	0	—	unchanged
Count node 1	node 2	1	—	unchanged
Count node 2	node 3	2	—	unchanged
Count node 3	node 4	3	—	unchanged
Count node 4	node 5	4	—	unchanged
Count node 5	null	5	—	unchanged
Target index = 5 - 2 = 3; reset curr	node 1	5	start at 1	head stays node 1
Seek predecessor	node 2	5	1 → 2	unchanged
Seek predecessor	node 3	5	2 → 3	loop ends: 3 is not less than 3
Bypass target	node 3	5	—	3.next: node 4 → node 5
Return head	node 3	5	—	[1,2,3,5]

Complexity Analysis

Time Complexity

O(L)

Space Complexity

O(1)

L denotes list length, while n denotes the requested position from the end. Counting performs L visits and seeking performs at most L advances. Only a counter and references are used; no nodes, arrays or recursion frames are allocated. The output reuses the original surviving nodes.

Code

Solution.java

1class ListNode {2    int val;3    ListNode next;4    ListNode(int val) { this.val = val; }5    ListNode(int val, ListNode next) { this.val = val; this.next = next; }6}7
8class Solution {9    public ListNode removeNthFromEnd(ListNode head, int n) {10        int length = 0;11        ListNode curr = head;12        while (curr != null) {13            length++;14            curr = curr.next;15        }16        // Target index length - n is zero, so removal changes the head.17        if (length == n) {18            return head.next;19        }20        curr = head;21        // Advance length - n - 1 times to stop at the target's predecessor.22        for (int i = 1; i < length - n; i++) {23            curr = curr.next;24        }25        curr.next = curr.next.next;26        return head;27    }28}

Hints

Hint 1

Translate the end-relative position into a forward position: with length L, the target is the node at one-based position L - n + 1.

Hint 2

Changing a singly linked list requires reaching the predecessor of the target; a dummy supplies the predecessor when the target is head.

Hint 3

Start both pointers at dummy and move the leader n + 1 links ahead. Preserve that link gap until the leader reaches null.

Edge Cases

Removing the head (n equals the length): left never leaves dummy, so the bypass still works.
A single-node list with n = 1: the bypass empties the list and dummy.next is null.
Removing the tail (n = 1) changes its predecessor.next to null; no surviving node should still reach the tail.
Duplicate values do not affect which position is removed; keep survivor identities and relative order.

Common Mistakes and Interview Tips

With the shown null-stopping convention, moving right only n links parks left on the target instead of its predecessor; a different stopping condition would be needed.
Returning the original head after removing it; return dummy.next in the gap approach or head.next in the two-pass head case.
Confusing the requested n with list length L when stating complexity or converting the target index.
Searching for a matching value instead of a position removes the wrong node when values repeat.
Clearing the target's next link before saving its successor loses the remaining suffix; the shown snippets bypass it without modifying that link.

Key Takeaway

A dummy node absorbs deletions at the head, and a fixed gap between two pointers converts distance-from-the-end into a one-pass location.