19. Remove Nth Node From End Of List

The Remove Nth Node From End of List (LeetCode 19) is a common linked list problem in FAANG interviews, including Amazon, Google, Microsoft, Meta, and Apple. Although it looks simple, it often challenges candidates because a singly linked list does not support backward traversal. Identifying a node from the end requires careful pointer manipulation and handling edge cases, especially when the head node must be removed.

The optimal solution uses the Two-Pointer (Fast and Slow) technique instead of a naive two-pass approach. By maintaining a gap of n nodes between the pointers, you can locate the target node’s predecessor in a single O(L) traversal, where L is the length of the list.

This pattern is fundamental in linked list interview problems, enabling solutions for tasks like finding the middle node or cycle detection. In top-tier interviews, the expected solution is a one-pass O(1) space approach, demonstrating strong control over efficient in-place algorithms and memory optimization.

Problem statement

You are given the head of a singly linked list. Your task is to remove the nth node counting from the end of the list and return the head of the modified list.

For example, if the list contains six nodes and n is 3, you need to find the third node from the tail, unlink it from the list, and return the updated list.

Constraints

• The number of nodes in the list is sz
• 1 ≤ sz ≤ 30
• 0 ≤ Node.val ≤ 100
• 1 ≤ n ≤ sz

Examples

Why naive approaches do not scale for removing the nth node from end of list

A straightforward approach is to traverse the linked list once to calculate its length, and then traverse it again to reach the node just before the target. While this two-pass solution is correct and runs in O(n) time, it requires two full traversals. In interviews, this problem is often used to assess whether you can optimize this into a single-pass solution using pointer manipulation, which demonstrates stronger algorithmic thinking.

Another naive approach is to convert the linked list into an array, remove the element by index, and rebuild the list. Although this works for small inputs, it uses O(n) extra space and avoids the core challenge of the problem, which is performing in-place linked list operations. In a technical interview, this approach typically indicates a lack of comfort with pointer-based solutions.

Optimized approach using two pointers

The two-pointer technique solves this problem in a single pass. The idea is to maintain a fixed gap of n nodes between two pointers, fast and slow. Both start at a dummy node placed before the head to simplify edge cases.

First, move fast ahead by n + 1 steps to create the required gap. Then advance both pointers one step at a time until fast reaches the end of the list. At this point, slow will be positioned exactly one node before the target node. You can then remove the target by updating slow.next to skip it.

The dummy node (sentinel) is important because it ensures consistent logic even when the node to be deleted is the head. This avoids special-case handling and keeps the algorithm clean and uniform across all inputs.

Why the optimized approach works well

The fixed gap between the two pointers is the key insight. When fast is n + 1 steps ahead of slow and both advance in lockstep, the gap never changes. So when fast reaches None (one step past the last node), slow is exactly n + 1 steps behind the end, which means slow.next is the nth node from the end. This invariant holds regardless of list length, which is what makes the approach robust.

The dummy node eliminates branching logic for the edge case where the head is removed. Since slow starts at the dummy, it can point to the node before head, allowing slow.next = slow.next.next to bypass the head just like any other node. This keeps the code simple and less error-prone.

Step-by-step algorithm

1. Create a dummy node with value 0 whose next pointer is set to head. This simplifies edge cases, especially when the head node needs to be removed.
2. Initialize two pointers, fast and slow, both starting at the dummy node.
3. Move the fast pointer ahead by n + 1 steps to create a fixed gap between fast and slow.
4. Move both pointers forward simultaneously, one step at a time, until fast reaches the end of the list (None). At each iteration, set fast = fast.next and slow = slow.next.
5. Now slow is the node immediately before the nth node from the end. Remove the target node by setting slow.next = slow.next.next, which bypasses it entirely.
6. Return dummy.next as the new head of the modified list, correctly handling cases where the original head is removed.

1 / 13

Python implementation

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


def remove_nth_last_node(head, n):
    # Create a dummy node to handle edge case of removing the head
    dummy = ListNode(0, head)
    # Initialize two pointers starting at the dummy node
    fast = dummy
    slow = dummy
    # Advance fast pointer n+1 steps ahead so the gap between fast and slow is n+1
    for _ in range(n + 1):
        fast = fast.next
    # Move both pointers until fast reaches the end
    while fast is not None:
        fast = fast.next
        slow = slow.next
    # slow is now pointing to the node just before the target node
    slow.next = slow.next.next
    # Return the head of the modified list (skip dummy)
    return dummy.next


def build_list(values):
    # Construct a linked list from a Python list of values
    dummy = ListNode(0)
    current = dummy
    for val in values:
        current.next = ListNode(val)
        current = current.next
    return dummy.next


def to_list(head):
    # Convert a linked list back into a Python list for easy display
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result


def main():
    test_cases = [
        ([10, 20, 30, 40, 50], 1),       # Remove last node
        ([5, 10, 15], 3),                 # Remove first node (head)
        ([7, 14, 21, 28], 2),             # Remove 2nd from end
        ([0, 1, 2, 3, 4, 5, 6], 4),      # Remove 4th from end
        ([99, 50], 2),                    # Remove head in a 2-element list
    ]
    for i, (values, n) in enumerate(test_cases, 1):
        head = build_list(values)
        result = remove_nth_last_node(head, n)
        print(f"{i}.\tInput list: {values}")
        print(f"\tn: {n}")
        print(f"\n\tResult: {to_list(result)}")
        print("-" * 80)


if __name__ == "__main__":
    main()

Time complexity

The time complexity is O(sz), where sz is the number of nodes in the linked list. In the first phase, the fast pointer advances n + 1 steps. In the second phase, both pointers advance together for the remaining sz - n steps. The total number of pointer moves is sz + 1, which simplifies to O(sz). The entire list is traversed exactly once.

Space complexity

The space complexity is O(1). The algorithm uses only a fixed number of extra pointers: dummy, fast, and slow. No additional data structures are allocated, and the size of these variables does not depend on the input length. There is no recursion, so there is no stack overhead to consider.

Edge cases

• Single-node list with n = 1: The only node must be removed, resulting in an empty list. The dummy node ensures this is handled cleanly since slow (at dummy) sets slow.next to None.
• Removing the head node (n equals the list length): When n equals sz, the first node must be removed. The dummy node allows slow to remain at the dummy position, and the reassignment slow.next = slow.next.next correctly bypasses the original head.
• Removing the last node (n = 1): The fast pointer advances only 2 steps initially, then both pointers walk until fast is None. slow ends up at the second-to-last node, and setting slow.next = None drops the tail.
• Two-node list: Whether n is 1 or 2, the algorithm correctly identifies and removes the target, leaving a single-node list.

Common pitfalls

• Forgetting the dummy node: Without a sentinel, removing the head node requires special-case logic. Many candidates either forget this case or introduce a bug by returning the original head even when it was removed.
• Advancing fast by n steps instead of n + 1: If you advance fast only n steps, then slow will land on the target node itself rather than the node before it. Since this is a singly linked list, you need to be at the predecessor to perform the removal.
• Off-by-one errors in the gap calculation: Miscounting the gap between pointers is the most common source of bugs. Drawing a small example on paper with 4 or 5 nodes and tracing the pointer positions step by step helps prevent this.
• Not returning dummy.next: Some candidates return head directly, which fails when the head was the node removed. Always return dummy.next to account for this.