Remove Nth Node From End of List (LC 19)

Pattern: Linked List — two pointers with gap
Difficulty: Medium
Key Concept: Advance a “fast” pointer n+1 steps ahead of “slow” behind a dummy; when fast hits null, slow is just before the node to remove.

Problem Statement

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

Input: head, integer n (1 ≤ n ≤ list length).
Output: head of modified list.

Example: 1 -> 2 -> 3 -> 4 -> 5, n = 2 → remove 4 → 1 -> 2 -> 3 -> 5.

---

1. Algorithm & Pseudocode

Brute force

1. First pass: count len by walking the list.
2. Remove node at index len - n from start (need predecessor).
3. Two passes, O(n) time, O(1) space—acceptable but not single-pass elegant.

Pseudocode:

len = count nodes
remove index = len - n
walk with prev to delete

Optimal (one pass, two pointers)

1. Create dummy with dummy.next = head to simplify removing head.
2. fast = slow = dummy.
3. Move fast forward n + 1 times (creates gap so slow ends before target).
4. Move both until fast == null.
5. slow.next = slow.next.next.

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why dummy: If the removed node is the first real node, you need a predecessor—dummy is that predecessor.

Why gap n + 1: When fast is null, slow should point to the node before the nth-from-end so you can relink next.

Why not compute length: One pass with two pointers avoids storing len (same asymptotic time, slightly cleaner).

---

3. The Dry Run

1 -> 2 -> 3 -> 4 -> 5, n = 2 (remove value 4). Dummy D.

After advancing fast n+1 = 3 steps from D:

pointer	position after init gap
slow	D
fast	node 2 (0-index from head: third step lands on 2)

Then advance both until fast == null:

step	slow at	fast at
…	…	…
end	node 3	null

slow is node 3; slow.next skips 4 → points to 5.

---

4. Java Solution

Brute Force

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int len = 0;
        for (ListNode p = head; p != null; p = p.next) {
            len++;
        }
        int skip = len - n;
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy;
        while (skip > 0) {
            cur = cur.next;
            skip--;
        }
        cur.next = cur.next.next;
        return dummy.next;
    }
}

Time: O(n). Space: O(1).

Optimal

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

Time: O(n). Space: O(1).

---

5. The “Java vs. Others” Edge

• ListNode(int val, ListNode next) constructor (Java) matches LeetCode 2024+ style; older snippets use manual next assignment.
• Single-pass is preferred in interviews when asked for “one scan.”
• Always return dummy.next in case head was removed.

---

6. Complexity Summary

Approach	Time	Space	Notes
Two-pass count	O(n)	O(1)	Easy to explain
Fast/slow one pass	O(n)	O(1)	Same complexity, elegant

---

ASCII — gap between slow and fast

Initial (n = 2, list length 5). Dummy D, gap keeps 3 nodes between slow and fast including the “extra” slot:

D        1        2        3        4        5
^slow                       ^fast

After moving both until fast == null:

                  slow              fast->null
                   |                  |
D --> 1 --> 2 --> 3 --> 4 --> 5 --> null
                   \___________/
                   skip this link: 3.next = 5

Result:

D --> 1 --> 2 --> 3 ---------> 5 --> null