Eliminate Node from Tail of Linked List

You're twenty minutes into a Meta phone screen when the interviewer asks you to remove the second-to-last node from a linked list in one pass. No length field. No random access. Just a pointer to the head and the number 2. On Firecode, we call this "Eliminate Node from Tail of Linked List," though you'll find it on other platforms under the name Remove Nth Node From End of List. It's a classic two-pointer problem that tests whether you can maintain a gap between two runners to locate a specific node without knowing the list length up front.

TL;DR

Use a dummy node and two pointers. Advance the first pointer n+1 steps ahead of the second to create a fixed gap. Then move both pointers forward until the first reaches null. At that point, the second pointer sits right before the target node. Rewire second.next to skip over it and return dummy.next. This runs in O(n) time and O(1) space in a single pass.

Why This Problem Matters

Removing the nth node from the end combines two patterns that show up everywhere in linked list interviews: the two-pointer gap technique and the dummy node trick. Companies like Meta, Google, and Amazon ask it because a single-pass constraint eliminates the "just count the length first" approach and forces you to think about relative positioning. Get comfortable with this, and you'll have the building blocks for cycle detection, middle-of-list problems, and partition operations.

Linked Lists: A Quick Refresher

A singly linked list is a chain of nodes where each node stores a value and a reference to the next node. You can only traverse forward, starting from the head.

Key characteristics to keep in mind:

• Head: The first node, your only entry point
• Tail: The last node, which points to null
• No random access: To reach the kth node, you walk through k-1 nodes first
• No length field: Unless you're maintaining one separately, you don't know the size without traversing

That "no random access" property is exactly what makes this problem interesting. In an array, removing the nth element from the end is trivial: compute array.length - n and you're done. With a linked list, you need a different strategy.

Understanding the Problem

Given: The head of a singly linked list and an integer n Task: Remove the nth node from the end of the list Return: The head of the modified list Constraint: 1 <= n <= length of list

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

Node 4 is the 2nd node from the end. After removing it:

Edge Cases to Consider

1. Single node, n = 1: Remove the only node, return null
2. Remove the head: When n equals the list length, the head itself must go
3. Remove the tail: When n = 1, remove the last node
4. Two nodes: A minimal list where off-by-one errors become visible

The "remove the head" case is the trickiest. Since the head has no preceding node, you'd normally need special-case logic. That's where the dummy node comes in.

Solution Approach

The Naive Two-Pass Method

The straightforward approach: traverse the list once to count its length, compute the position from the front (length - n), traverse again to that position, and remove. This works, runs in O(n) time, and is perfectly valid.

But the follow-up question is always: "Can you do it in one pass?"

The Single-Pass Two-Pointer Technique

The idea is to maintain two pointers separated by a gap of exactly n nodes. When the leading pointer reaches the end of the list, the trailing pointer is sitting right before the node you want to remove.

Here's the plan:

1. Create a dummy node and point its next to the head
2. Place both pointers (first and second) at the dummy node
3. Advance first by n + 1 steps to open up a gap
4. Move both pointers forward until first hits null
5. second is now one node before the target - rewire to skip it
6. Return dummy.next

Why n+1 Steps?

You need second to land one node before the target so you can adjust second.next. If you only advanced first by n steps, second would end up on the target itself, and you'd have no way to update the preceding node's pointer.

The Dummy Node

Prepending a dummy node before the head means every real node - including the head - has a predecessor. This eliminates the special case for head removal entirely.

Tracing Through the Algorithm

For [1, 2, 3, 4, 5] with n = 2, here's how the pointers move:

After the first pointer advances n + 1 = 3 steps, the pointers are separated:

first is at node 3 (index 3), second is at the dummy (index 0) - a gap of 3 positions

Both pointers then advance in lockstep. When first reaches null, second is at node 3:

first has gone past node 5 (null), second is at node 3 - one step before the target (node 4)

Now second.next = second.next.next skips node 4, and we're done.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public ListNode removeNthFromEnd(ListNode head, int n) {
    // Dummy node handles the edge case of removing the head
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    // Both pointers start at the dummy
    ListNode first = dummy;
    ListNode second = dummy;

    // Open a gap of n+1 between first and second
    for (int i = 0; i <= n; i++) {
      first = first.next;
    }

    // Move both pointers until first falls off the end
    while (first != null) {
      first = first.next;
      second = second.next;
    }

    // second is now one node before the target - skip over it
    second.next = second.next.next;

    // Return dummy.next, not head (head might have been removed)
    return dummy.next;
  }
}

A few things worth noting in this implementation:

• dummy.next = head links the dummy into the existing list without copying anything
• The for loop uses i <= n, which means it runs n + 1 times, giving us the right gap
• return dummy.next is critical - if the head was removed, head still points to the old (now disconnected) first node

Complexity Analysis

Time Complexity: O(n)

The first pointer traverses the entire list exactly once. The second pointer traverses most of the list. Every node is visited at most twice (once by each pointer), so the total work is proportional to the list length.

Space Complexity: O(1)

We use a fixed number of pointer variables (dummy, first, second) plus one dummy node. None of these scale with input size. No recursion, no auxiliary data structures.

Comparison with Two-Pass Approach

Both approaches are O(n) time and O(1) space. The single-pass version isn't asymptotically faster, but it touches each node fewer times. In practice, the performance difference is negligible. The real reason interviewers prefer it is that it demonstrates a useful technique - the fixed-gap two-pointer pattern - that applies to many other linked list problems.

Common Pitfalls

1. Forgetting the dummy node: Without it, removing the head requires an if check that's easy to get wrong. The dummy costs one extra node allocation and saves you from a bug.

2. Advancing by n instead of n+1: This lands second on the target node itself rather than one node before it. You can't remove a node if you're standing on it - you need to be one step back to rewire the next pointer.

3. Returning head instead of dummy.next: When the head is removed, head still references the old first node. dummy.next always points to the true head of the modified list.

4. Off-by-one in the gap loop: Using i < n instead of i <= n creates a gap that's one node too short, causing the wrong node to be removed.

Interview Tips

When this problem comes up:

1. Clarify the constraint: "Is n guaranteed to be valid, or should I handle the case where n exceeds the list length?" (In most formulations, n is always valid.)

2. Mention both approaches: "I could do this in two passes by counting the length first, but the single-pass two-pointer approach is more interesting. Would you like me to implement that?"

3. Draw the dummy node: Sketch the dummy pointing to the head on a whiteboard. Trace through a small example like [1, 2, 3] with n = 1 and n = 3 to verify edge cases.

4. Call out the gap size: Explicitly say "I advance first by n+1, not n, because I want second to end up one node before the target."

5. Test the head-removal case: Walk through what happens when n equals the length. The dummy node should handle it naturally. If it doesn't, there's a bug.

Key Takeaways

• The fixed-gap two-pointer technique finds the nth node from the end in a single pass by maintaining a gap of n+1 between two pointers.
• A dummy node before the head eliminates special-case logic for head removal. It costs one extra allocation and saves you from the most common bug in this problem.
• Always return dummy.next instead of head, because the head may have been the node that was removed.
• This pattern transfers directly to related problems: finding the middle node (slow/fast pointers), detecting cycles (Floyd's algorithm), and partitioning a list around a value.
• Test with three inputs: remove the tail (n = 1), remove the head (n = length), and a middle node. These three cases cover the primary edge cases.

Practice Makes Perfect

Once you're comfortable with this problem, try these related linked list challenges:

• Reverse a linked list (the fundamental pointer manipulation problem)
• Find the middle of a linked list (another two-pointer technique)
• Detect a cycle in a linked list (Floyd's tortoise and hare)
• Merge two sorted linked lists (pointer rewiring under different constraints)

This problem and hundreds of others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed roles at top tech companies. Whether you're brushing up on linked list fundamentals or grinding through two-pointer problems before your next phone screen, consistent practice is what turns these patterns into muscle memory.

Solutions in Other Languages

Python

class Solution:
    def remove_nth_from_end(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        first = dummy
        second = dummy

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

        while first is not None:
            first = first.next
            second = second.next

        second.next = second.next.next
        return dummy.next

JavaScript

class Solution {
  removeNthFromEnd(head, n) {
    let dummy = new ListNode(0);
    dummy.next = head;
    let first = dummy;
    let second = dummy;

    for (let i = 0; i <= n; i++) {
      first = first.next;
    }

    while (first !== null) {
      first = first.next;
      second = second.next;
    }

    second.next = second.next.next;
    return dummy.next;
  }
}

TypeScript

class Solution {
  removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    const dummy = new ListNode(0);
    dummy.next = head;
    let first: ListNode | null = dummy;
    let second: ListNode | null = dummy;

    for (let i = 0; i <= n; i++) {
      first = first!.next;
    }

    while (first !== null) {
      first = first.next;
      second = second!.next;
    }

    second!.next = second!.next!.next;
    return dummy.next;
  }
}

C++

In C++, you should also free the memory of the removed node to avoid leaks:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0, head);
        ListNode* first = &dummy;
        ListNode* second = &dummy;

        for (int i = 0; i <= n; ++i) {
            first = first->next;
        }

        while (first != nullptr) {
            first = first->next;
            second = second->next;
        }

        ListNode* nodeToRemove = second->next;
        second->next = second->next->next;
        delete nodeToRemove;

        return dummy.next;
    }
};

Go

func (s *Solution) RemoveNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    first := dummy
    second := dummy

    for i := 0; i <= n; i++ {
        first = first.Next
    }

    for first != nil {
        first = first.Next
        second = second.Next
    }

    second.Next = second.Next.Next
    return dummy.Next
}

Scala

class Solution {
  def removeNthFromEnd(head: ListNode, n: Int): ListNode = {
    val dummy = ListNode(0, head)
    var first = dummy
    var second = dummy

    for (_ <- 0 to n) {
      first = first.next
    }

    while (first != null) {
      first = first.next
      second = second.next
    }

    second.next = second.next.next
    dummy.next
  }
}

Kotlin

class Solution {
  fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
    val dummy = ListNode(0)
    dummy.next = head
    var first: ListNode? = dummy
    var second: ListNode? = dummy

    repeat(n + 1) {
      first = first?.next
    }

    while (first != null) {
      first = first?.next
      second = second?.next
    }

    second!!.next = second!!.next?.next
    return dummy.next
  }
}

Swift

class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        let dummy = ListNode(0)
        dummy.next = head
        var first: ListNode? = dummy
        var second: ListNode? = dummy

        for _ in 0...n {
            first = first?.next
        }

        while first != nil {
            first = first?.next
            second = second?.next
        }

        second!.next = second!.next?.next
        return dummy.next
    }
}

Ruby

class Solution
  def remove_nth_from_end(head, n)
    dummy = ListNode.new(0)
    dummy.next = head
    first = dummy
    second = dummy

    (n + 1).times { first = first.next }

    while first
      first = first.next
      second = second.next
    end

    second.next = second.next.next
    dummy.next
  end
end

C#

public class Solution {
    public ListNode? RemoveNthFromEnd(ListNode? head, int n) {
        var dummy = new ListNode(0);
        dummy.next = head;
        ListNode? first = dummy;
        ListNode? second = dummy;

        for (int i = 0; i <= n; i++) {
            first = first.next;
        }

        while (first != null) {
            first = first.next;
            second = second.next;
        }

        second.next = second.next.next;
        return dummy.next;
    }
}

Dart

class Solution {
  ListNode? removeNthFromEnd(ListNode? head, int n) {
    ListNode dummy = ListNode(0);
    dummy.next = head;
    ListNode? first = dummy;
    ListNode? second = dummy;

    for (int i = 0; i <= n; i++) {
      first = first?.next;
    }

    while (first != null) {
      first = first?.next;
      second = second?.next;
    }

    second!.next = second!.next?.next;
    return dummy.next;
  }
}

PHP

class Solution {
    public function removeNthFromEnd(?ListNode $head, int $n): ?ListNode {
        $dummy = new ListNode(0);
        $dummy->next = $head;
        $first = $dummy;
        $second = $dummy;

        for ($i = 0; $i <= $n; $i++) {
            $first = $first->next;
        }

        while ($first !== null) {
            $first = $first->next;
            $second = $second->next;
        }

        $second->next = $second->next->next;
        return $dummy->next;
    }
}

Rust

Rust's ownership model makes direct two-pointer manipulation on linked lists more complex. The idiomatic approach counts the length first, then removes the target node:

impl Solution {
    pub fn remove_nth_from_end(&self, head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut dummy = Box::new(ListNode::new(0));
        dummy.next = head;

        let length = {
            let mut count = 0;
            let mut current = &dummy.next;
            while let Some(ref node) = current {
                count += 1;
                current = &node.next;
            }
            count
        };

        let target = length - n as usize;
        let mut current = &mut dummy;
        for _ in 0..target {
            current = current.next.as_mut().unwrap();
        }

        let next_next = current.next.as_mut().unwrap().next.take();
        current.next = next_next;

        dummy.next
    }
}