JustPaste.it

Remove Nth Node From End of List (LeetCode 19): One Pass With a Gap of N

This is one of those linked list questions interviewers love because the brute-force answer is easy and the follow-up ("can you do it in one pass?") separates people who have actually practiced pointer gaps.

The problem

Given the head of a singly linked list, remove the n-th node from the end and return the head. Example: 1 -> 2 -> 3 -> 4 -> 5, n = 2 gives 1 -> 2 -> 3 -> 5.

Two passes (fine, but not the answer they want)

Count the length L, then walk L - n steps and unlink the next node. It is O(L) time and O(1) space, but it reads the list twice.

One pass: keep two pointers n nodes apart

  1. Put a dummy node in front of the head. This removes the special case where the head itself is deleted.
  2. Move fast n steps ahead of slow (both start at the dummy).
  3. Move both together until fast.next is null. Now slow.next is the node to delete.
  4. slow.next = slow.next.next, return dummy.next.
def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

Gotchas interviewers check

  • Deleting the head (n == L): without the dummy node you need an if. With it, slow stays on the dummy and the code just works.
  • Off-by-one in the gap: you want slow to stop on the node before the target, so the loop condition is fast.next, not fast.
  • Single-node list: [1], n = 1 should return an empty list. Test it out loud.

Complexity

O(L) time, one traversal, O(1) extra space.

Practicing this pattern

The "gap of n" trick shows up again in middle-of-list, cycle detection and rotate-list problems, so say the invariant out loud: "fast is always n nodes ahead of slow." If you want a second pair of eyes during mock rounds, I work on Linkjob AI copilot, a real-time interview helper; disclosure: I'm on the team that builds it.