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

Watch the gap between fast and slow: it opens up to n while slow holds still, then both advance together and the gap never changes, so the moment fast reaches the last node slow is sitting one node before the target.

phaseinit

gap0

remove—

slowfasttarget

1 / 8

currentcomparingdiscardedresult

indigo = slow · amber = fast

Start with a dummy node D before the head so removing the real head is never special. Both pointers sit on D, so the gap is 0.

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.

Remove Nth Node From End of List

Two Pass: Compute Length First

One Pass: Two Pointers With a Gap

More Linked List practice