Remove Nth Node From End of List

Solving tips

For the single-pass solution, use two pointers kept exactly n apart: when the fast one runs off the end, the slow one is at the victim's predecessor.
Start slow at a dummy node and fast at the head, then advance fast n steps first; the dummy makes head deletion a non-special case.
The key off-by-one: you want slow to land on the predecessor, not the victim, so mind exactly where each pointer starts and where fast stops.
Target O(sz) time in one pass with O(1) space; return dummy.next, never head.

Problem

Given the head of a singly linked list and an integer n, delete the node that sits n positions from the end of the list (so n = 1 means the last node), and return the head of the modified list.

The follow-up asks: can you do it in a single pass over the list?

Examples

Input: head = [1, 2, 3, 4, 5], n = 2 → Output: [1, 2, 3, 5] The 2nd node from the end is 4; it is removed.
Input: head = [1], n = 1 → Output: [] The only node is also the 1st from the end; removing it empties the list.
Input: head = [1, 2], n = 2 → Output: [2] The 2nd from the end is the head itself.

Constraints

1 <= sz <= 30 where sz is the number of nodes, and 1 <= n <= sz.
0 <= Node.val <= 100.
n is always valid, so no “n too large” handling is needed — but the deleted node can be the head.

Think about it first

Hint 1

"n from the end" is the same as "(length − n + 1) from the start". What is the simplest way to get the length?

Hint 2

For one pass: if two pointers walk together while staying exactly n nodes apart, where is the trailing pointer when the leading one falls off the end?

Hint 3

Start both pointers at a dummy node before the head. Advance the fast pointer n+1 steps... or more simply: advance fast n steps, then move both until fast reaches the last node — slow now sits just *before* the victim, and the dummy handles head deletion.

TL;DR

Two pointers kept exactly n apart find the predecessor of the victim in one pass — O(sz) time, O(1) space.

Approach 1 — Brute force: array of nodes

Store every node in a Python list; the victim’s predecessor is then a direct index away.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        nodes: List[ListNode] = []
        node = head
        while node:
            nodes.append(node)
            node = node.next
        idx = len(nodes) - n          # index of the victim
        if idx == 0:
            return head.next          # victim is the head
        nodes[idx - 1].next = nodes[idx].next
        return head

Time O(sz), space O(sz). With sz <= 30 nothing kills it — the O(sz) node array is just pointless bookkeeping compared to what a second pointer can do, and it fails the one-pass follow-up.

Approach 2 — Two passes: count, then walk

Insight: “n from the end” is “(L − n + 1) from the start”. Pass one measures the length L; pass two walks to node L − n’s predecessor. A dummy node in front of the head means the predecessor always exists, even when the head is deleted.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        length = 0
        node = head
        while node:
            length += 1
            node = node.next
        dummy = ListNode(0, head)
        prev = dummy
        for _ in range(length - n):   # steps to the victim's predecessor
            prev = prev.next
        prev.next = prev.next.next
        return dummy.next

Walkthrough on [1, 2, 3, 4, 5], n = 2: length = 5; walk 5 − 2 = 3 steps from the dummy → prev is node 3; splice out node 4 → [1, 2, 3, 5].

Time O(sz) (two passes), space O(1).

Approach 3 — One pass: gap of n between two pointers (optimal)

Insight: you don’t need the length — you need a pointer that reaches the victim’s predecessor exactly when another pointer reaches the last node. Give fast a head start of n nodes from the head while slow waits at the dummy; then march both together until fast steps off the list. The gap is preserved, so slow lands n+1 nodes from the end: the predecessor.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        slow, fast = dummy, head
        for _ in range(n):            # open a gap of n
            fast = fast.next
        while fast:                   # slide the gap to the end
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next    # slow is the predecessor
        return dummy.next

Walkthrough on [1, 2, 3, 4, 5], n = 2:

step	slow	fast
gap opened	dummy	3
slide 1	1	4
slide 2	2	5
slide 3	3	None

slow = 3, so slow.next = 5, giving [1, 2, 3, 5]. On [1], n = 1: fast starts past the end (None), the slide loop never runs, slow = dummy, and dummy.next = None — the empty list, no special case needed.

Time O(sz) in a single pass, space O(1).

Common pitfalls

Deleting the head: any version without a dummy node needs an explicit if branch — the dummy makes [1], n = 1 and [1,2], n = 2 fall out for free.
Off-by-one in the gap: starting slow at the dummy but fast at the head is what bakes in the extra +1 so slow stops at the predecessor, not the victim. Start both at the same node and you’ll stop one node late.
Stopping the slide at fast.next vs fast — be consistent with where fast started, and trace a 2-node example before trusting it.
Returning head instead of dummy.next — wrong whenever the head was the deleted node.

Pattern takeaway

A fixed offset from the end of a singly linked list is found in one pass by two pointers separated by that offset: when the leader exhausts the list, the trailer is at the target. Combine with a dummy predecessor whenever the operation is a deletion, and the head stops being a special case.