Remove Nth From End LeetCode 19 Guide

LeetCode 19 — Remove Nth Node From End of List — asks you to remove the nth node counting from the end of a singly linked list and return the modified head. The challenge constraint is to do it in one pass, which rules out counting the length first and makes it a classic two-pointer problem.

The problem is labeled Medium and appears frequently in FAANG interviews because it tests whether candidates can reason about relative pointer positions in a linked list without needing to know its length up front.

Key constraints to keep in mind: n is always valid (1 ≤ n ≤ list length), the list has between 1 and 30 nodes, node values are between 0 and 100, and you must handle the edge case where the node to remove is the head itself.

The straightforward solution uses two passes. In the first pass, traverse the entire list to count its length L. In the second pass, traverse to position L − n to find the node just before the target, then set its next pointer to skip over the target node.

This approach is easy to implement and understand. For a list of length L, the node to remove is at position L − n (0-indexed from the head). You walk to that position, then update the next pointer: prev.next = prev.next.next.

The two-pass solution works correctly but misses the one-pass optimization the problem explicitly asks for. The interviewer callout: the one-pass trick is to advance the fast pointer n steps ahead of slow at the start, then move both together until fast reaches the end — at that point slow is exactly at the node before the target.

The one-pass solution uses two pointers — fast and slow — both starting at a dummy node placed before the head. The key is to advance fast exactly n + 1 steps ahead of slow. Then move both pointers forward one step at a time until fast becomes null.

At that moment, slow is pointing to the node immediately before the nth-from-end node. Setting slow.next = slow.next.next effectively removes the target node from the list. Return dummy.next as the new head.

This works because the gap of n + 1 between the pointers ensures that when fast falls off the end of the list (null), slow is exactly one position before the node to delete — giving you the predecessor pointer you need for removal.

The dummy node is not just a convenience — it is necessary for correctness. Consider the case where n equals the length of the list, meaning you need to remove the head node. Without a dummy node, there is no predecessor to update; you would need a special case to handle head removal.

By prepending a dummy node before the actual head, slow always starts one step before the list. This guarantees that slow can always point to the node before the target, even when the target is the first real node. The dummy node makes the removal logic uniform for every position in the list.

After the removal, returning dummy.next gives you the correct new head — whether the original head was removed or not. This is a standard linked list pattern that shows up in many list manipulation problems.

Trace through the list 1 → 2 → 3 → 4 → 5 with n = 2. We want to remove the 2nd node from the end, which is node 4. After removal the list should be 1 → 2 → 3 → 5.

Start: dummy → 1 → 2 → 3 → 4 → 5, both fast and slow at dummy. Advance fast by n + 1 = 3 steps: fast is now at node 3. Move both together: fast goes to node 4, slow to node 1; fast goes to node 5, slow to node 2; fast goes to null, slow to node 3. Now slow is at node 3, which is right before the target node 4.

Execute slow.next = slow.next.next: slow.next was node 4, now it points to node 5. Node 4 is removed. Return dummy.next which is node 1. Final list: 1 → 2 → 3 → 5. The algorithm handled it correctly with a single traversal.

In Python: create a ListNode dummy with dummy.next = head. Set fast = slow = dummy. Loop n + 1 times advancing fast. Then while fast is not None, advance both fast and slow. Set slow.next = slow.next.next. Return dummy.next. Time complexity O(n), space complexity O(1). The entire solution is about 10 lines.

In Java: the pattern is identical — create a dummy ListNode, initialize both pointers to dummy, advance fast n + 1 times in a for loop, then use a while (fast != null) loop to move both, finally set slow.next = slow.next.next and return dummy.next. The dummy node's val can be 0 or any value since it is never part of the output.

Both implementations run in O(n) time with a single pass and use O(1) extra space — only two pointers and the dummy node are allocated. This is the optimal solution for this problem.

Remove Nth Node From End belongs to the linked list two-pointer family. Linked List Cycle II (LeetCode 142) also uses fast and slow pointers with a deliberate gap — fast moves twice as fast as slow to detect cycles. Reverse Linked List II (LeetCode 92) reverses a sublist within bounds, requiring careful pointer surgery similar to the removal here.

Reorder List (LeetCode 143) combines multiple linked list skills: find the midpoint with slow/fast pointers, reverse the second half, then merge the two halves. If you are comfortable with Remove Nth Node, Reorder List is the natural next step.

The broader two-pointer linked list family shares a common theme: use pointer separation or speed differences to locate positions relative to the end or middle of the list without knowing its length in advance. Mastering the n-gap and 2x-speed patterns unlocks the entire category.