Remove Nth Node From End of List

Difficulty: Medium Source: NeetCode

Problem

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

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

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

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

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Linked List Traversal — walking a list and counting nodes
• Two-Pointer Technique — maintaining a gap between two pointers
• Dummy Head Trick — using a sentinel node to handle edge cases like removing the head

1. Brute Force / Naive Approach

Intuition

First, figure out the total length of the list. Then the nth node from the end is at position length - n from the start (0-indexed). Walk to that position and remove it. Straightforward and easy to reason about, but requires two full passes.

Algorithm

1. Walk the list to get its length L.
2. The target node is at index L - n (0-indexed from head).
3. Walk to index L - n - 1 (the node just before the target).
4. Skip the target: prev.next = prev.next.next.
5. Handle the special case where the target is the head itself (L - n == 0).

Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "None")

def removeNthFromEnd_brute(head, n):
    # First pass: get length
    length = 0
    cur = head
    while cur:
        length += 1
        cur = cur.next

    # The node to remove is at index (length - n) from the start (0-indexed)
    target_idx = length - n

    # Special case: removing the head
    if target_idx == 0:
        return head.next

    # Second pass: walk to node just before target
    cur = head
    for _ in range(target_idx - 1):
        cur = cur.next

    cur.next = cur.next.next  # skip the target node
    return head

# Test cases
head = build_list([1, 2, 3, 4, 5])
print("Output: ", end=""); print_list(removeNthFromEnd_brute(head, 2))  # 1->2->3->5

head2 = build_list([1])
print("Output: ", end=""); print_list(removeNthFromEnd_brute(head2, 1))  # None

head3 = build_list([1, 2])
print("Output: ", end=""); print_list(removeNthFromEnd_brute(head3, 1))  # 1

Complexity

• Time: O(n) — two passes over the list
• Space: O(1) — no extra data structures

2. Two-Pointer One-Pass (Optimal)

Intuition

We can do this in a single pass by maintaining a gap of exactly n nodes between two pointers. Here’s the trick:

• Advance the fast pointer n steps ahead.
• Then move both slow and fast together until fast.next is None.
• At that point, slow is sitting just before the node to remove.

Using a dummy head means we never have to special-case removing the actual head node.

head = [1, 2, 3, 4, 5], n = 2

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
slow = dummy, fast = dummy

Advance fast 2 steps:
fast = 2  (dummy, 1, 2 -- that's 2 steps from dummy)

Move both until fast.next is None:
slow=1, fast=3
slow=2, fast=4
slow=3, fast=5  (fast.next is None, stop)

slow.next is 4 (the 2nd from end) -- remove it:
slow.next = slow.next.next  →  3 -> 5

Result: 1 -> 2 -> 3 -> 5

Algorithm

1. Create a dummy node pointing to head. Set slow = dummy and fast = dummy.
2. Advance fast exactly n steps forward.
3. Move both slow and fast one step at a time until fast.next is None.
4. Remove slow.next: slow.next = slow.next.next.
5. Return dummy.next.

Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "None")

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)  # dummy.next = head
    slow = dummy
    fast = dummy

    # Advance fast by n steps
    for _ in range(n):
        fast = fast.next

    # Move both until fast.next is None
    while fast.next:
        slow = slow.next
        fast = fast.next

    # slow.next is the node to remove
    slow.next = slow.next.next

    return dummy.next

# Test cases
head = build_list([1, 2, 3, 4, 5])
print("Output: ", end=""); print_list(removeNthFromEnd(head, 2))  # 1->2->3->5

head2 = build_list([1])
print("Output: ", end=""); print_list(removeNthFromEnd(head2, 1))  # None

head3 = build_list([1, 2])
print("Output: ", end=""); print_list(removeNthFromEnd(head3, 1))  # 1

head4 = build_list([1, 2])
print("Output: ", end=""); print_list(removeNthFromEnd(head4, 2))  # 2 (remove head)

head5 = build_list([1, 2, 3, 4, 5])
print("Output: ", end=""); print_list(removeNthFromEnd(head5, 5))  # 2->3->4->5 (remove head)

Complexity

• Time: O(sz) — single pass
• Space: O(1) — only pointer variables

Common Pitfalls

Not using a dummy node and forgetting the head-removal edge case. If the list has only one node and n=1, the result should be None. Without a dummy, you need a special if branch. The dummy node makes slow always point to the node before the one to delete, even when deleting the head.

Advancing fast by n+1 instead of n. Some formulations advance fast by n+1 from a dummy start and then stop when fast is None. Both work, but they’re different — be consistent. In our approach: advance by n, then stop when fast.next is None.

Off-by-one in the gap. The gap between slow and fast should be such that when fast reaches the last node (not past it), slow is at the node before the one to remove. Trace through a small example to verify your gap is correct.