Remove Nth Node From End of List

The tricky part is that “nth from the end” is awkward for a singly linked list, since you cannot walk backward from the tail. The straightforward fix is to first measure the list’s length. The one-pass trick is to use two pointers that stay a fixed gap of n apart, so when the leading one hits the end, the trailing one is sitting exactly where it needs to remove a node.

Two Pass: Compute Length First

Time O(n)Space O(1)

Walk the list once to count its length L. The node to remove is at position L - n from the front (0-indexed). Walk again to that position — using a dummy node before head so that removing the head itself does not need a special case — and unlink it.

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

class Solution:
    def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
        length = 0
        node = head
        while node:
            length += 1
            node = node.next

        dummy = ListNode(0, head)
        prev = dummy
        for _ in range(length - n):
            prev = prev.next
        prev.next = prev.next.next
        return dummy.next

Correct and easy to reason about, but it touches the list twice — once to measure, once to remove. The follow-up asks for a single pass.

One Pass: Two Pointers With a Gap

OptimalTime O(n)Space O(1)

Advance a fast pointer n steps ahead of slow first. Then move both forward together, one step at a time. When fast reaches the last node, slow is exactly n nodes behind it — one step before the node that needs removing. A dummy head handles the case where the node to remove is the actual head.

class Solution:
    def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
        dummy = ListNode(0, head)
        fast = slow = dummy

        for _ in range(n):        # open up a gap of n nodes
            fast = fast.next

        while fast.next:          # move both until fast falls off the end
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next
        return dummy.next

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

▲slow

▲fast

1 / 5

Both start at dummy (D). fast moves n=2 steps ahead to node 2. slow stays at dummy.

Why it’s correct: after opening a gap of n nodes and advancing both pointers together, the distance between slow and fast stays fixed at n — so when fast reaches the last node, slow is n nodes behind the end, i.e., one node before the target. Complexity: a single pass through the list with two pointers → O(n) time, O(1) space — this satisfies the one-pass follow-up and is optimal, since the list’s length must be discovered by visiting nodes at least once.