LeetCode · #19

Remove Nth Node From End of List Solution

Given the head, remove the nth node from the end and return the head.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #19

🏗️

Pattern

Two Pointers — n-gap technique

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

Example

 Input: 1 → 2 → 3 → 4 → 5,  n = 2 Output: 1 → 2 → 3 → 5 // Removed node 4 (2nd from end) 

Constraints

 • 1 ≤ sz ≤ 30 • 0 ≤ Node.val ≤ 100 • 1 ≤ n ≤ sz 

Section Two · Approach 1

Two Pass — O(n)

First pass: count the total length L. Second pass: advance L-n steps to the node before the target, then skip over it. Two traversals.

Can we do it in one pass? Yes — the n-gap technique uses two pointers separated by n nodes. When the leading pointer reaches the end, the trailing pointer is at the node before the target.

Section Three · Approach 2

One-Pass Two Pointers — O(n)

Advance a fast pointer n steps ahead. Then move both fast and slow together. When fast reaches the end, slow is right before the target node. Delete by slow.next = slow.next.next.

💡 Mental model: Imagine two people walking in a hallway, n steps apart. When the leader reaches the wall, the follower is exactly n steps from the wall — standing right before the node you want to remove.

Algorithm

Step 1: Create a dummy node pointing to head (handles edge case of removing head).
Step 2: fast = dummy, slow = dummy. Advance fast n+1 steps.
Step 3: Move both until fast reaches null.
Step 4: slow.next = slow.next.next (delete target).
Step 5: Return dummy.next.

🎯 Why a dummy node?:

If we're removing the head (n == list length), there's no node before the head.
A dummy node before head gives us something to link from.
Without it, we'd need a special case for removing the first node.

Section Four · Trace

Visual Walkthrough

Trace: 1→2→3→4→5, n=2:

N-gap two pointers — fast leads by n+1

Section Five · Implementation

Code — Java & Python

Java — One-pass with dummy

 class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode fast = dummy, slow = dummy;
for (int i = 0; i <= n; i++) // n+1 steps
fast = fast.next;
while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next; // delete target return dummy.next;
    }
}

Python — One-pass with dummy

 class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        fast = slow = dummy
for _ in range(n + 1):
            fast = fast.next
while fast:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next
return dummy.next

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Two Pass	O(n)	O(1)	Count then remove — two traversals
One Pass ← optimal	O(n)	O(1)	Single traversal, n-gap pointers

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Remove head	`[1], n=1`	Only node → remove it → return null. Dummy handles this.
Remove first node	`[1,2], n=2`	n == length. slow stays at dummy → dummy.next = 2.
Remove last	`[1,2,3], n=1`	slow ends at node 2, skips node 3.

⚠ Common Mistake: Advancing fast only n steps instead of n+1. We need slow to land one node before the target so we can skip it. With n steps, slow lands at the target — too late to delete it.

← Back to Linked List problems

LearningTree

LC 19 · Remove Nth Node From End of List — Solution & Explanation | DSA Guide