Remove Nth Node From End of Linked List

Removing a node from a singly linked list is straightforward when you know its position from the start. But what about from the end? You don’t know the length until you’ve traversed the entire list. The naive approach makes two passes — one to find the length, one to find the target. The elegant approach uses two pointers separated by a gap of n nodes to do it in a single pass.

Problem statement

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

LeetCode 19 — Remove Nth Node From End of Linked List

Constraints:

• The number of nodes is sz where 1 {'<'}= sz {'<'}= 30
• 1 {'<'}= n {'<'}= sz

Examples:

Input:  1 -> 2 -> 3 -> 4 -> 5,  n = 2
Output: 1 -> 2 -> 3 -> 5
(Removed node 4, which is 2nd from the end)

Input:  1,  n = 1
Output: None
(Removed the only node)

Input:  1 -> 2,  n = 1
Output: 1
(Removed the tail)

Node definition

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

---

Approach 1: Two-pass (find length first)

Intuition

If the list has L nodes and we want to remove the nth from the end, that’s the (L - n + 1)th from the start (1-indexed). So find L first, then walk to position L - n to find the node before the target.

Implementation

def remove_nth_from_end_two_pass(head: ListNode, n: int) -> ListNode:
    # Pass 1: Find the length
    length = 0
    current = head
    while current:
        length += 1
        current = current.next

    # Edge case: removing the head
    if n == length:
        return head.next

    # Pass 2: Walk to the node before the target
    current = head
    for _ in range(length - n - 1):
        current = current.next

    # Skip over the target node
    current.next = current.next.next

    return head

Walkthrough

List: 1 -> 2 -> 3 -> 4 -> 5,  n = 2

Pass 1: length = 5
Target from start: 5 - 2 + 1 = 4th node (value 4)
Node before target: position 3 (value 3)

Pass 2: Walk to position 3
  current = 1, step 0
  current = 2, step 1
  current = 3, step 2  => stop

current.next = current.next.next
  3.next was 4, now 3.next = 5

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

Complexity

Metric	Value
Time	O(n) — at most two full passes (still linear)
Space	O(1) — only pointer variables

---

Approach 2: One-pass with two pointers (the gap technique)

Intuition

Place two pointers n nodes apart. When the fast pointer reaches the end, the slow pointer is exactly at the node before the one we want to remove.

The trick: use a dummy node before head. This handles the edge case where we need to remove the head itself — without it, we’d need special-case logic.

Visual explanation

n = 2
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None

Step 1: Advance fast pointer n+1 steps from dummy
  fast moves to: dummy -> 1 -> 2 -> 3
                                      ^fast
  slow stays at: dummy
                  ^slow

Step 2: Move both until fast reaches None
  Iteration 1: slow=1, fast=4
  Iteration 2: slow=2, fast=5
  Iteration 3: slow=3, fast=None  => stop

Step 3: slow.next = slow.next.next
  3.next was 4, now 3.next = 5

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

Why the gap works

Think of it this way. If fast is n nodes ahead of slow, and fast is at the last node, then slow is n nodes behind the last node. That puts slow right before the nth-from-end node — exactly where we need it for deletion.

Implementation

def remove_nth_from_end(head: ListNode, n: int) -> ListNode:
    # Create a dummy node pointing to head
    dummy = ListNode(0, head)

    # Initialize both pointers at the dummy
    slow = dummy
    fast = dummy

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

    # Move both pointers until fast reaches the end
    while fast:
        slow = slow.next
        fast = fast.next

    # slow is now right before the target — skip it
    slow.next = slow.next.next

    return dummy.next

Step-by-step trace

List: 1 -> 2 -> 3 -> 4 -> 5,  n = 2

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
  ^slow
  ^fast

After advancing fast by 3 (n+1) steps:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
  ^slow              ^fast

Moving both:
  slow=1, fast=4
  slow=2, fast=5
  slow=3, fast=None  => stop

slow.next = slow.next.next
  Before: 3 -> 4 -> 5
  After:  3 -> 5

return dummy.next => 1 -> 2 -> 3 -> 5

Complexity

Metric	Value
Time	O(n) — single pass through the list
Space	O(1) — only pointer variables (dummy node is O(1))

---

The dummy node trick explained

The dummy node is one of the most useful patterns in linked list problems. Here’s why it matters:

Without dummy node — removing the head is a special case

# Without dummy: we need an explicit check
def remove_nth_no_dummy(head: ListNode, n: int) -> ListNode:
    fast = head
    for _ in range(n):
        fast = fast.next

    # If fast is None, we're removing the head
    if fast is None:
        return head.next

    slow = head
    while fast.next:
        slow = slow.next
        fast = fast.next

    slow.next = slow.next.next
    return head

With dummy node — no special cases

The dummy node ensures slow always has a node before the target, even when the target is the head. The code becomes cleaner and less error-prone.

Removing head (n = length):

Without dummy:
  head -> 1 -> 2 -> 3
  fast advances n steps and becomes None
  Need special check: if fast is None, return head.next

With dummy:
  dummy -> 1 -> 2 -> 3
  ^slow
  fast advances n+1 steps
  When fast is None, slow is at dummy
  slow.next = slow.next.next skips head naturally

Rule of thumb: Whenever a linked list problem might require modifying the head, start with a dummy node.

---

Edge cases deep dive

Case 1: Single node, remove it

List: 1 -> None,  n = 1

dummy -> 1 -> None
  ^slow
  ^fast

Fast advances 2 steps: fast = None

slow = dummy, slow.next = slow.next.next = None

return dummy.next = None  (empty list)

Case 2: Remove the head of a multi-node list

List: 1 -> 2 -> 3,  n = 3

dummy -> 1 -> 2 -> 3 -> None
  ^slow
  ^fast

Fast advances 4 steps: fast = None

slow = dummy
slow.next = slow.next.next = node 2

return dummy.next = 2 -> 3

Case 3: Remove the tail

List: 1 -> 2 -> 3,  n = 1

dummy -> 1 -> 2 -> 3 -> None
  ^slow
  ^fast

Fast advances 2 steps: fast = 1

Move both until fast.next is None... wait, we move until fast is None:
  slow=1, fast=2
  slow=2, fast=3
  slow=2... hmm.

Let me retrace with the correct algorithm:
Fast advances n+1 = 2 steps from dummy:
  fast = node 2

Move both until fast is None:
  slow=1, fast=3
  slow=2, fast=None => stop

slow.next = slow.next.next
  2.next was 3, now 2.next = None

return dummy.next = 1 -> 2

---

Common mistakes

1. Off-by-one on the gap. The fast pointer needs to advance n + 1 steps from dummy (not n), so that slow ends up before the target, not on it.

2. Forgetting to return dummy.next. If you return head, you’ll miss the case where the head was removed.

3. Not using a dummy node. This leads to messy special-case code for head removal. Always use a dummy for deletion problems.

4. Assuming n is valid. The problem guarantees 1 {'<'}= n {'<'}= sz, but in production code you’d want to validate n.

Variations and follow-ups

Remove nth node from end — return the removed node

def remove_and_return_nth(head: ListNode, n: int) -> tuple:
    """Returns (new_head, removed_node)."""
    dummy = ListNode(0, head)
    slow, fast = dummy, dummy

    for _ in range(n + 1):
        fast = fast.next

    while fast:
        slow = slow.next
        fast = fast.next

    removed = slow.next
    slow.next = slow.next.next
    removed.next = None  # Clean up the removed node

    return dummy.next, removed

What if you’re given the node to remove (not n)?

That’s a different problem — LeetCode 237: Delete Node in a Linked List. You copy the next node’s value into the current node and skip the next node. But you can’t delete the tail this way.

---

Practice problems

Problem	Difficulty	Link
Remove Nth Node From End of List	Medium	LeetCode 19
Delete Node in a Linked List	Medium	LeetCode 237
Middle of the Linked List	Easy	LeetCode 876
Linked List Cycle	Easy	LeetCode 141
Remove Linked List Elements	Easy	LeetCode 203
Swapping Nodes in a Linked List	Medium	LeetCode 1721

Key takeaways

• The two-pointer gap technique is a fundamental pattern. By maintaining a fixed distance between two pointers, you can locate positions relative to the end without knowing the list’s length.
• The dummy node eliminates head-modification edge cases. Use it whenever a problem might require changing the head of the list.
• Even though the two-pass solution is also O(n), the single-pass solution is preferred in interviews because it demonstrates the gap technique — a pattern that applies to many other problems.
• Always test your solution against the three critical edge cases: removing the head, removing the tail, and removing from a single-node list.