Remove Nth Node From End of List

Problem Statement

Given the head of a linked list, remove the nth node from the end of the list and return the head of the modified list.

You must solve this in one pass when possible, but a two-pass solution is a good warm-up.

What to notice first

• The key challenge is identifying the node before the one you want to remove, not the node itself.
• Removing the head is a special case — the result is head.next.
• Using a dummy node elegantly handles the head removal case without branching.
• The “one pass” constraint forces you to maintain a gap between two pointers.

Examples

Input	n	Output	Explanation
1 → 2 → 3 → 4 → 5	2	1 → 2 → 3 → 5	The 4th node (value 4) is removed.
1	1	(empty)	Single node is removed; result is empty.
1 → 2	1	1	Remove the 2nd node (end); result is [1].
1 → 2	2	2	Remove the 1st node (head); result is [2].

Constraints

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 < n <= sz
• All node values are unique.

Real-World Applications

Where this pattern appears

• Circular buffer eviction — remove the nth most recent element to implement an LRU cache.
• Audio playback — skip the nth song from the end of a playlist queue.
• Undo/redo stacks — remove the nth action from the end of the history when memory is limited.
• Log rotation — discard the nth oldest log entry when the buffer is full.
• Packet processing — drop the nth packet from the back of a transmission queue.

Complexity Comparison

Approach	Time	Space	Passes	Best When
Two Pass	O(L)	O(1)	2	Learning the basic algorithm or when clarity is prioritized
Two Pointers (One Pass)	O(L)	O(1)	1	Interview setting or when single-pass constraint is required

Which approach should you learn first?

• Pick Two Pass if you are learning linked list concepts for the first time.
• Pick Two Pointers if you want the optimal solution or are in an interview where “one pass” is mentioned.

Single Pass (Optimal)

Two Pointers

O(L) time · O(1) space

Easier to Understand

Two Pass

O(L) time · O(1) space

Approach 1: Two Pass

✓ Simple

Count the total number of nodes in the first pass, then find and skip the target node in the second pass.

This approach is straightforward: first measure the list, then navigate to the node before the one to remove.

⏱ Time O(L) Two passes 💾 Space O(1)

Step-by-step Example

Input: 1 → 2 → 3 → 4 → 5, n = 2

Pass 1 (Count): Length = 5

Pass 2 (Remove): We want to skip the node at position 5 - 2 = 3 from the start (0-indexed: position 3).

• Navigate to position 2 (the node with value 3).
• Set node.next = node.next.next (skip the 4).
• Result: 1 → 2 → 3 → 5

Another case: n = 1 (remove the last node)

Pass 1 (Count): Length = 5

Pass 2 (Remove): We want to skip the node at position 5 - 1 = 4 from the start.

• Navigate to position 3 (the node with value 4).
• Set node.next = node.next.next (skip the 5).
• Result: 1 → 2 → 3 → 4

Edge case: 1, n = 1 (remove the only node)

Pass 1 (Count): Length = 1

Since length == n, return head.next, which is null.

• Result: (empty list)

Pseudocode

function removeNthNodeTwoPass(head, n):
    // First pass: count total nodes
    length = 0
    current = head
    while current != null:
        length++
        current = current.next

    // Edge case: removing the head
    if length == n:
        return head.next

    // Second pass: find the node before the one to remove
    current = head
    for i from 0 to length - n - 2:
        current = current.next

    // Remove the nth node
    current.next = current.next.next
    return head

Solution Code

Python

remove_nth_node_from_end_of_list_two_pass.py

from typing import Optional


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


def remove_nth_node_two_pass(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    """
    Remove the nth node from the end of a linked list using two passes.

    Approach:
    1. First pass: count the total number of nodes
    2. Second pass: find and skip the nth node from the end

    Time: O(L) + O(L-n) = O(L)
    Space: O(1)
    """
    # First pass: count the total nodes
    length = 0
    current = head
    while current:
        length += 1
        current = current.next

    # Edge case: removing the head node
    if length == n:
        return head.next

    # Second pass: find the node before the one to remove
    current = head
    for i in range(length - n - 1):
        current = current.next

    # Remove the nth node
    current.next = current.next.next
    return head


# Helper function to create a linked list from a list
def create_linked_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


# Helper function to convert linked list to list for easy printing
def linked_list_to_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result


# Test cases
if __name__ == "__main__":
    # Test 1: [1, 2, 3, 4, 5], n=2
    head1 = create_linked_list([1, 2, 3, 4, 5])
    result1 = remove_nth_node_two_pass(head1, 2)
    print(linked_list_to_list(result1))  # [1, 2, 3, 5]

    # Test 2: [1], n=1
    head2 = create_linked_list([1])
    result2 = remove_nth_node_two_pass(head2, 1)
    print(linked_list_to_list(result2))  # []

    # Test 3: [1, 2], n=2
    head3 = create_linked_list([1, 2])
    result3 = remove_nth_node_two_pass(head3, 2)
    print(linked_list_to_list(result3))  # [2]

    # Test 4: [1, 2], n=1
    head4 = create_linked_list([1, 2])
    result4 = remove_nth_node_two_pass(head4, 1)
    print(linked_list_to_list(result4))  # [1]

C++

remove_nth_node_from_end_of_list_two_pass.cpp

#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x = 0, ListNode *n = nullptr) : val(x), next(n) {}
};

ListNode *remove_nth_node_two_pass(ListNode *head, int n) {
    /**
     * Remove the nth node from the end of a linked list using two passes.
     *
     * Approach:
     * 1. First pass: count the total number of nodes
     * 2. Second pass: find and skip the nth node from the end
     *
     * Time: O(L) + O(L-n) = O(L)
     * Space: O(1)
     */

    // First pass: count the total nodes
    int length = 0;
    ListNode *current = head;
    while (current) {
        length++;
        current = current->next;
    }

    // Edge case: removing the head node
    if (length == n) {
        ListNode *new_head = head->next;
        delete head;
        return new_head;
    }

    // Second pass: find the node before the one to remove
    current = head;
    for (int i = 0; i < length - n - 1; i++) {
        current = current->next;
    }

    // Remove the nth node
    ListNode *temp = current->next;
    current->next = current->next->next;
    delete temp;
    return head;
}

// Helper function to create a linked list from a vector
ListNode *create_linked_list(vector<int> &values) {
    if (values.empty())
        return nullptr;
    ListNode *head = new ListNode(values[0]);
    ListNode *current = head;
    for (int i = 1; i < values.size(); i++) {
        current->next = new ListNode(values[i]);
        current = current->next;
    }
    return head;
}

// Helper function to convert linked list to vector for easy printing
vector<int> linked_list_to_vector(ListNode *head) {
    vector<int> result;
    ListNode *current = head;
    while (current) {
        result.push_back(current->val);
        current = current->next;
    }
    return result;
}

// Helper function to print a vector
void print_vector(const vector<int> &v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i];
        if (i < v.size() - 1)
            cout << ", ";
    }
    cout << "]" << endl;
}

// Test cases
int main() {
    // Test 1: [1, 2, 3, 4, 5], n=2
    vector<int> vals1 = {1, 2, 3, 4, 5};
    ListNode *head1 = create_linked_list(vals1);
    ListNode *result1 = remove_nth_node_two_pass(head1, 2);
    print_vector(linked_list_to_vector(result1));  // [1, 2, 3, 5]

    // Test 2: [1], n=1
    vector<int> vals2 = {1};
    ListNode *head2 = create_linked_list(vals2);
    ListNode *result2 = remove_nth_node_two_pass(head2, 1);
    print_vector(linked_list_to_vector(result2));  // []

    // Test 3: [1, 2], n=2
    vector<int> vals3 = {1, 2};
    ListNode *head3 = create_linked_list(vals3);
    ListNode *result3 = remove_nth_node_two_pass(head3, 2);
    print_vector(linked_list_to_vector(result3));  // [2]

    // Test 4: [1, 2], n=1
    vector<int> vals4 = {1, 2};
    ListNode *head4 = create_linked_list(vals4);
    ListNode *result4 = remove_nth_node_two_pass(head4, 1);
    print_vector(linked_list_to_vector(result4));  // [1]

    return 0;
}

Java

remove_nth_node_from_end_of_list_two_pass.java

public class remove_nth_node_from_end_of_list_two_pass {

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * Remove the nth node from the end of a linked list using two passes.
     *
     * Approach:
     * 1. First pass: count the total number of nodes
     * 2. Second pass: find and skip the nth node from the end
     *
     * Time: O(L) + O(L-n) = O(L)
     * Space: O(1)
     */
    public static ListNode removeNthNode(ListNode head, int n) {
        // First pass: count the total nodes
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }

        // Edge case: removing the head node
        if (length == n) {
            return head.next;
        }

        // Second pass: find the node before the one to remove
        current = head;
        for (int i = 0; i < length - n - 1; i++) {
            current = current.next;
        }

        // Remove the nth node
        current.next = current.next.next;
        return head;
    }

    // Helper function to create a linked list from an array
    static ListNode createLinkedList(int[] values) {
        if (values.length == 0)
            return null;
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }

    // Helper function to convert linked list to string for easy printing
    static String linkedListToString(ListNode head) {
        StringBuilder result = new StringBuilder("[");
        ListNode current = head;
        while (current != null) {
            result.append(current.val);
            current = current.next;
            if (current != null) {
                result.append(", ");
            }
        }
        result.append("]");
        return result.toString();
    }

    // Test cases
    public static void main(String[] args) {
        // Test 1: [1, 2, 3, 4, 5], n=2
        ListNode head1 = createLinkedList(new int[]{1, 2, 3, 4, 5});
        ListNode result1 = removeNthNode(head1, 2);
        System.out.println(linkedListToString(result1));  // [1, 2, 3, 5]

        // Test 2: [1], n=1
        ListNode head2 = createLinkedList(new int[]{1});
        ListNode result2 = removeNthNode(head2, 1);
        System.out.println(linkedListToString(result2));  // []

        // Test 3: [1, 2], n=2
        ListNode head3 = createLinkedList(new int[]{1, 2});
        ListNode result3 = removeNthNode(head3, 2);
        System.out.println(linkedListToString(result3));  // [2]

        // Test 4: [1, 2], n=1
        ListNode head4 = createLinkedList(new int[]{1, 2});
        ListNode result4 = removeNthNode(head4, 1);
        System.out.println(linkedListToString(result4));  // [1]
    }
}

JavaScript

remove_nth_node_from_end_of_list_two_pass.js

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Remove the nth node from the end of a linked list using two passes.
 *
 * Approach:
 * 1. First pass: count the total number of nodes
 * 2. Second pass: find and skip the nth node from the end
 *
 * Time: O(L) + O(L-n) = O(L)
 * Space: O(1)
 *
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
function removeNthNodeTwoPass(head, n) {
    // First pass: count the total nodes
    let length = 0;
    let current = head;
    while (current) {
        length++;
        current = current.next;
    }

    // Edge case: removing the head node
    if (length === n) {
        return head.next;
    }

    // Second pass: find the node before the one to remove
    current = head;
    for (let i = 0; i < length - n - 1; i++) {
        current = current.next;
    }

    // Remove the nth node
    current.next = current.next.next;
    return head;
}

// Helper function to create a linked list from an array
function createLinkedList(values) {
    if (values.length === 0) return null;
    const head = new ListNode(values[0]);
    let current = head;
    for (let i = 1; i < values.length; i++) {
        current.next = new ListNode(values[i]);
        current = current.next;
    }
    return head;
}

// Helper function to convert linked list to array for easy printing
function linkedListToArray(head) {
    const result = [];
    let current = head;
    while (current) {
        result.push(current.val);
        current = current.next;
    }
    return result;
}

// Test cases
if (require.main === module) {
    // Test 1: [1, 2, 3, 4, 5], n=2
    const head1 = createLinkedList([1, 2, 3, 4, 5]);
    const result1 = removeNthNodeTwoPass(head1, 2);
    console.log(linkedListToArray(result1));  // [1, 2, 3, 5]

    // Test 2: [1], n=1
    const head2 = createLinkedList([1]);
    const result2 = removeNthNodeTwoPass(head2, 1);
    console.log(linkedListToArray(result2));  // []

    // Test 3: [1, 2], n=2
    const head3 = createLinkedList([1, 2]);
    const result3 = removeNthNodeTwoPass(head3, 2);
    console.log(linkedListToArray(result3));  // [2]

    // Test 4: [1, 2], n=1
    const head4 = createLinkedList([1, 2]);
    const result4 = removeNthNodeTwoPass(head4, 1);
    console.log(linkedListToArray(result4));  // [1]
}

module.exports = removeNthNodeTwoPass;

Rust

remove_nth_node_from_end_of_list_two_pass.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Rc<RefCell<ListNode>>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

/*
Remove the nth node from the end of a linked list using two passes.

Approach:
1. First pass: count the total number of nodes
2. Second pass: find and skip the nth node from the end

Time: O(L) + O(L-n) = O(L)
Space: O(1)
*/
pub fn remove_nth_node_two_pass(head: Option<Rc<RefCell<ListNode>>>, n: i32) -> Option<Rc<RefCell<ListNode>>> {
    // First pass: count the total nodes
    let mut length = 0;
    let mut current = head.as_ref();
    while let Some(node) = current {
        length += 1;
        current = node.borrow().next.as_ref();
    }

    // Edge case: removing the head node
    if length == n {
        return head.and_then(|node| node.borrow_mut().next.take());
    }

    // Second pass: find the node before the one to remove
    if let Some(head_node) = head {
        let mut current = Some(head_node.clone());
        for _ in 0..length - n - 1 {
            if let Some(node) = current {
                current = node.borrow_mut().next.take();
            }
        }

        if let Some(node) = current {
            let mut borrowed = node.borrow_mut();
            if let Some(next) = borrowed.next.take() {
                borrowed.next = next.borrow_mut().next.take();
            }
        }

        return Some(head_node);
    }

    None
}

// Helper function to create a linked list from a vector
pub fn create_linked_list(values: Vec<i32>) -> Option<Rc<RefCell<ListNode>>> {
    if values.is_empty() {
        return None;
    }

    let head = Rc::new(RefCell::new(ListNode::new(values[0])));
    let mut current = head.clone();

    for i in 1..values.len() {
        let new_node = Rc::new(RefCell::new(ListNode::new(values[i])));
        current.borrow_mut().next = Some(new_node.clone());
        current = new_node;
    }

    Some(head)
}

// Helper function to convert linked list to vector for easy printing
pub fn linked_list_to_vec(head: Option<Rc<RefCell<ListNode>>>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut current = head;

    while let Some(node) = current {
        result.push(node.borrow().val);
        current = node.borrow_mut().next.take();
    }

    result
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_remove_nth_node() {
        // Test 1: [1, 2, 3, 4, 5], n=2
        let head1 = create_linked_list(vec![1, 2, 3, 4, 5]);
        let result1 = remove_nth_node_two_pass(head1, 2);
        assert_eq!(linked_list_to_vec(result1), vec![1, 2, 3, 5]);

        // Test 2: [1], n=1
        let head2 = create_linked_list(vec![1]);
        let result2 = remove_nth_node_two_pass(head2, 1);
        assert_eq!(linked_list_to_vec(result2), vec![]);

        // Test 3: [1, 2], n=2
        let head3 = create_linked_list(vec![1, 2]);
        let result3 = remove_nth_node_two_pass(head3, 2);
        assert_eq!(linked_list_to_vec(result3), vec![2]);

        // Test 4: [1, 2], n=1
        let head4 = create_linked_list(vec![1, 2]);
        let result4 = remove_nth_node_two_pass(head4, 1);
        assert_eq!(linked_list_to_vec(result4), vec![1]);
    }
}

Go

remove_nth_node_from_end_of_list_two_pass.go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

/*
Remove the nth node from the end of a linked list using two passes.

Approach:
1. First pass: count the total number of nodes
2. Second pass: find and skip the nth node from the end

Time: O(L) + O(L-n) = O(L)
Space: O(1)
*/
func removeNthNodeTwoPass(head *ListNode, n int) *ListNode {
    // First pass: count the total nodes
    length := 0
    current := head
    for current != nil {
        length++
        current = current.Next
    }

    // Edge case: removing the head node
    if length == n {
        return head.Next
    }

    // Second pass: find the node before the one to remove
    current = head
    for i := 0; i < length-n-1; i++ {
        current = current.Next
    }

    // Remove the nth node
    current.Next = current.Next.Next
    return head
}

// Helper function to create a linked list from a slice
func createLinkedList(values []int) *ListNode {
    if len(values) == 0 {
        return nil
    }
    head := &ListNode{Val: values[0]}
    current := head
    for i := 1; i < len(values); i++ {
        current.Next = &ListNode{Val: values[i]}
        current = current.Next
    }
    return head
}

// Helper function to convert linked list to slice for easy printing
func linkedListToSlice(head *ListNode) []int {
    var result []int
    current := head
    for current != nil {
        result = append(result, current.Val)
        current = current.Next
    }
    return result
}

// Test cases
func main() {
    // Test 1: [1, 2, 3, 4, 5], n=2
    head1 := createLinkedList([]int{1, 2, 3, 4, 5})
    result1 := removeNthNodeTwoPass(head1, 2)
    fmt.Println(linkedListToSlice(result1))  // [1 2 3 5]

    // Test 2: [1], n=1
    head2 := createLinkedList([]int{1})
    result2 := removeNthNodeTwoPass(head2, 1)
    fmt.Println(linkedListToSlice(result2))  // []

    // Test 3: [1, 2], n=2
    head3 := createLinkedList([]int{1, 2})
    result3 := removeNthNodeTwoPass(head3, 2)
    fmt.Println(linkedListToSlice(result3))  // [2]

    // Test 4: [1, 2], n=1
    head4 := createLinkedList([]int{1, 2})
    result4 := removeNthNodeTwoPass(head4, 1)
    fmt.Println(linkedListToSlice(result4))  // [1]
}

Approach 2: Two Pointers (One Pass - Recommended)

★ Recommended

Use a dummy node and two pointers (fast and slow) with a controlled gap. Move both pointers in lockstep; when the fast pointer reaches the end, the slow pointer will be at the node before the one to remove.

The dummy node is the key: it cleanly handles the edge case of removing the head without special branching.

⏱ Time O(L) Single pass 💾 Space O(1)

Step-by-step Example

Input: 1 → 2 → 3 → 4 → 5, n = 2

Setup: Create dummy: 0 → 1 → 2 → 3 → 4 → 5

• Slow = dummy, fast = dummy

Move fast pointer n+1 = 3 steps ahead:

• Step 1: fast = 1
• Step 2: fast = 2
• Step 3: fast = 3

Now there is a gap of 2 nodes between slow (dummy) and fast (3).

Move both pointers until fast reaches the end:

• Move 1: slow = 1, fast = 4
• Move 2: slow = 2, fast = 5
• Move 3: slow = 3, fast = null

Fast is now null. Slow is at node 3.

Remove the next node: slow.next = slow.next.next

• 3.next = 5 (skip 4)

Result: 0 → 1 → 2 → 3 → 5, return dummy.next = 1 → 2 → 3 → 5

Edge case: 1 → 2, n = 2 (remove the head)

Setup: Create dummy: 0 → 1 → 2

• Slow = dummy, fast = dummy

Move fast pointer n+1 = 3 steps ahead:

• Step 1: fast = 1
• Step 2: fast = 2
• Step 3: fast = null

Move both pointers until fast reaches the end:

• fast is already null, so the loop does not run.

Remove the next node: slow.next = slow.next.next

• dummy.next = 2 (skip 1)

Result: 0 → 2, return dummy.next = 2

Pseudocode

function removeNthNodeTwoPointers(head, n):
    dummy = new Node(0)
    dummy.next = head
    slow = dummy
    fast = dummy

    // Move fast pointer n+1 steps ahead
    for i from 0 to n:
        if fast == null:
            return head
        fast = fast.next

    // Move both pointers until fast reaches the end
    while fast != null:
        slow = slow.next
        fast = fast.next

    // Remove the nth node
    slow.next = slow.next.next
    return dummy.next

Solution Code

Python

remove_nth_node_from_end_of_list_two_pointers.py

from typing import Optional


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


def remove_nth_node_two_pointers(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    """
    Remove the nth node from the end of a linked list using two pointers in one pass.

    Approach:
    1. Create a dummy node pointing to head (handles edge case of removing head)
    2. Use fast and slow pointers with a gap of n nodes between them
    3. Move both pointers until fast reaches the end
    4. Skip the target node by adjusting the slow pointer

    Time: O(L) single pass
    Space: O(1)
    """
    # Create a dummy node to handle edge case of removing the head
    dummy = ListNode(0)
    dummy.next = head
    slow = dummy
    fast = dummy

    # Move fast pointer n+1 steps ahead
    for i in range(n + 1):
        if not fast:
            return head
        fast = fast.next

    # Move both pointers until fast reaches the end
    while fast:
        slow = slow.next
        fast = fast.next

    # Remove the nth node
    slow.next = slow.next.next
    return dummy.next


# Helper function to create a linked list from a list
def create_linked_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


# Helper function to convert linked list to list for easy printing
def linked_list_to_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result


# Test cases
if __name__ == "__main__":
    # Test 1: [1, 2, 3, 4, 5], n=2
    head1 = create_linked_list([1, 2, 3, 4, 5])
    result1 = remove_nth_node_two_pointers(head1, 2)
    print(linked_list_to_list(result1))  # [1, 2, 3, 5]

    # Test 2: [1], n=1
    head2 = create_linked_list([1])
    result2 = remove_nth_node_two_pointers(head2, 1)
    print(linked_list_to_list(result2))  # []

    # Test 3: [1, 2], n=2
    head3 = create_linked_list([1, 2])
    result3 = remove_nth_node_two_pointers(head3, 2)
    print(linked_list_to_list(result3))  # [2]

    # Test 4: [1, 2], n=1
    head4 = create_linked_list([1, 2])
    result4 = remove_nth_node_two_pointers(head4, 1)
    print(linked_list_to_list(result4))  # [1]

C++

remove_nth_node_from_end_of_list_two_pointers.cpp

#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x = 0, ListNode *n = nullptr) : val(x), next(n) {}
};

ListNode *remove_nth_node_two_pointers(ListNode *head, int n) {
    /**
     * Remove the nth node from the end of a linked list using two pointers in one
     * pass.
     *
     * Approach:
     * 1. Create a dummy node pointing to head (handles edge case of removing head)
     * 2. Use fast and slow pointers with a gap of n nodes between them
     * 3. Move both pointers until fast reaches the end
     * 4. Skip the target node by adjusting the slow pointer
     *
     * Time: O(L) single pass
     * Space: O(1)
     */

    // Create a dummy node to handle edge case of removing the head
    ListNode *dummy = new ListNode(0);
    dummy->next = head;
    ListNode *slow = dummy;
    ListNode *fast = dummy;

    // Move fast pointer n+1 steps ahead
    for (int i = 0; i <= n; i++) {
        if (!fast)
            return head;
        fast = fast->next;
    }

    // Move both pointers until fast reaches the end
    while (fast) {
        slow = slow->next;
        fast = fast->next;
    }

    // Remove the nth node
    ListNode *temp = slow->next;
    slow->next = slow->next->next;
    delete temp;
    ListNode *result = dummy->next;
    delete dummy;
    return result;
}

// Helper function to create a linked list from a vector
ListNode *create_linked_list(vector<int> &values) {
    if (values.empty())
        return nullptr;
    ListNode *head = new ListNode(values[0]);
    ListNode *current = head;
    for (int i = 1; i < values.size(); i++) {
        current->next = new ListNode(values[i]);
        current = current->next;
    }
    return head;
}

// Helper function to convert linked list to vector for easy printing
vector<int> linked_list_to_vector(ListNode *head) {
    vector<int> result;
    ListNode *current = head;
    while (current) {
        result.push_back(current->val);
        current = current->next;
    }
    return result;
}

// Helper function to print a vector
void print_vector(const vector<int> &v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i];
        if (i < v.size() - 1)
            cout << ", ";
    }
    cout << "]" << endl;
}

// Test cases
int main() {
    // Test 1: [1, 2, 3, 4, 5], n=2
    vector<int> vals1 = {1, 2, 3, 4, 5};
    ListNode *head1 = create_linked_list(vals1);
    ListNode *result1 = remove_nth_node_two_pointers(head1, 2);
    print_vector(linked_list_to_vector(result1));  // [1, 2, 3, 5]

    // Test 2: [1], n=1
    vector<int> vals2 = {1};
    ListNode *head2 = create_linked_list(vals2);
    ListNode *result2 = remove_nth_node_two_pointers(head2, 1);
    print_vector(linked_list_to_vector(result2));  // []

    // Test 3: [1, 2], n=2
    vector<int> vals3 = {1, 2};
    ListNode *head3 = create_linked_list(vals3);
    ListNode *result3 = remove_nth_node_two_pointers(head3, 2);
    print_vector(linked_list_to_vector(result3));  // [2]

    // Test 4: [1, 2], n=1
    vector<int> vals4 = {1, 2};
    ListNode *head4 = create_linked_list(vals4);
    ListNode *result4 = remove_nth_node_two_pointers(head4, 1);
    print_vector(linked_list_to_vector(result4));  // [1]

    return 0;
}

Java

remove_nth_node_from_end_of_list_two_pointers.java

public class remove_nth_node_from_end_of_list_two_pointers {

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * Remove the nth node from the end of a linked list using two pointers in one
     * pass.
     *
     * Approach:
     * 1. Create a dummy node pointing to head (handles edge case of removing head)
     * 2. Use fast and slow pointers with a gap of n nodes between them
     * 3. Move both pointers until fast reaches the end
     * 4. Skip the target node by adjusting the slow pointer
     *
     * Time: O(L) single pass
     * Space: O(1)
     */
    public static ListNode removeNthNode(ListNode head, int n) {
        // Create a dummy node to handle edge case of removing the head
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;

        // Move fast pointer n+1 steps ahead
        for (int i = 0; i <= n; i++) {
            if (fast == null)
                return head;
            fast = fast.next;
        }

        // Move both pointers until fast reaches the end
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // Remove the nth node
        slow.next = slow.next.next;
        return dummy.next;
    }

    // Helper function to create a linked list from an array
    static ListNode createLinkedList(int[] values) {
        if (values.length == 0)
            return null;
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }

    // Helper function to convert linked list to string for easy printing
    static String linkedListToString(ListNode head) {
        StringBuilder result = new StringBuilder("[");
        ListNode current = head;
        while (current != null) {
            result.append(current.val);
            current = current.next;
            if (current != null) {
                result.append(", ");
            }
        }
        result.append("]");
        return result.toString();
    }

    // Test cases
    public static void main(String[] args) {
        // Test 1: [1, 2, 3, 4, 5], n=2
        ListNode head1 = createLinkedList(new int[]{1, 2, 3, 4, 5});
        ListNode result1 = removeNthNode(head1, 2);
        System.out.println(linkedListToString(result1));  // [1, 2, 3, 5]

        // Test 2: [1], n=1
        ListNode head2 = createLinkedList(new int[]{1});
        ListNode result2 = removeNthNode(head2, 1);
        System.out.println(linkedListToString(result2));  // []

        // Test 3: [1, 2], n=2
        ListNode head3 = createLinkedList(new int[]{1, 2});
        ListNode result3 = removeNthNode(head3, 2);
        System.out.println(linkedListToString(result3));  // [2]

        // Test 4: [1, 2], n=1
        ListNode head4 = createLinkedList(new int[]{1, 2});
        ListNode result4 = removeNthNode(head4, 1);
        System.out.println(linkedListToString(result4));  // [1]
    }
}

JavaScript

remove_nth_node_from_end_of_list_two_pointers.js

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Remove the nth node from the end of a linked list using two pointers in one
 * pass.
 *
 * Approach:
 * 1. Create a dummy node pointing to head (handles edge case of removing head)
 * 2. Use fast and slow pointers with a gap of n nodes between them
 * 3. Move both pointers until fast reaches the end
 * 4. Skip the target node by adjusting the slow pointer
 *
 * Time: O(L) single pass
 * Space: O(1)
 *
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
function removeNthNodeTwoPointers(head, n) {
    // Create a dummy node to handle edge case of removing the head
    const dummy = new ListNode(0);
    dummy.next = head;
    let slow = dummy;
    let fast = dummy;

    // Move fast pointer n+1 steps ahead
    for (let i = 0; i <= n; i++) {
        if (!fast) return head;
        fast = fast.next;
    }

    // Move both pointers until fast reaches the end
    while (fast) {
        slow = slow.next;
        fast = fast.next;
    }

    // Remove the nth node
    slow.next = slow.next.next;
    return dummy.next;
}

// Helper function to create a linked list from an array
function createLinkedList(values) {
    if (values.length === 0) return null;
    const head = new ListNode(values[0]);
    let current = head;
    for (let i = 1; i < values.length; i++) {
        current.next = new ListNode(values[i]);
        current = current.next;
    }
    return head;
}

// Helper function to convert linked list to array for easy printing
function linkedListToArray(head) {
    const result = [];
    let current = head;
    while (current) {
        result.push(current.val);
        current = current.next;
    }
    return result;
}

// Test cases
if (require.main === module) {
    // Test 1: [1, 2, 3, 4, 5], n=2
    const head1 = createLinkedList([1, 2, 3, 4, 5]);
    const result1 = removeNthNodeTwoPointers(head1, 2);
    console.log(linkedListToArray(result1));  // [1, 2, 3, 5]

    // Test 2: [1], n=1
    const head2 = createLinkedList([1]);
    const result2 = removeNthNodeTwoPointers(head2, 1);
    console.log(linkedListToArray(result2));  // []

    // Test 3: [1, 2], n=2
    const head3 = createLinkedList([1, 2]);
    const result3 = removeNthNodeTwoPointers(head3, 2);
    console.log(linkedListToArray(result3));  // [2]

    // Test 4: [1, 2], n=1
    const head4 = createLinkedList([1, 2]);
    const result4 = removeNthNodeTwoPointers(head4, 1);
    console.log(linkedListToArray(result4));  // [1]
}

module.exports = removeNthNodeTwoPointers;

Rust

remove_nth_node_from_end_of_list_two_pointers.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Rc<RefCell<ListNode>>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

/*
Remove the nth node from the end of a linked list using two pointers in one pass.

Approach:
1. Create a dummy node pointing to head (handles edge case of removing head)
2. Use fast and slow pointers with a gap of n nodes between them
3. Move both pointers until fast reaches the end
4. Skip the target node by adjusting the slow pointer

Time: O(L) single pass
Space: O(1)
*/
pub fn remove_nth_node_two_pointers(
    head: Option<Rc<RefCell<ListNode>>>,
    n: i32,
) -> Option<Rc<RefCell<ListNode>>> {
    let dummy = Rc::new(RefCell::new(ListNode::new(0)));
    dummy.borrow_mut().next = head;

    let mut slow = dummy.clone();
    let mut fast = dummy.clone();

    // Move fast pointer n+1 steps ahead
    for _ in 0..=n {
        if fast.borrow().next.is_none() {
            return dummy.borrow_mut().next.take();
        }
        let next = fast.borrow_mut().next.take();
        if let Some(node) = next {
            fast = node;
        }
    }

    // Move both pointers until fast reaches the end
    loop {
        if fast.borrow().next.is_none() {
            break;
        }
        let slow_next = slow.borrow_mut().next.take();
        if let Some(node) = slow_next {
            slow = node;
        }
        let fast_next = fast.borrow_mut().next.take();
        if let Some(node) = fast_next {
            fast = node;
        }
    }

    // Remove the nth node
    if let Some(next_node) = slow.borrow_mut().next.take() {
        slow.borrow_mut().next = next_node.borrow_mut().next.take();
    }

    dummy.borrow_mut().next.take()
}

// Helper function to create a linked list from a vector
pub fn create_linked_list(values: Vec<i32>) -> Option<Rc<RefCell<ListNode>>> {
    if values.is_empty() {
        return None;
    }

    let head = Rc::new(RefCell::new(ListNode::new(values[0])));
    let mut current = head.clone();

    for i in 1..values.len() {
        let new_node = Rc::new(RefCell::new(ListNode::new(values[i])));
        current.borrow_mut().next = Some(new_node.clone());
        current = new_node;
    }

    Some(head)
}

// Helper function to convert linked list to vector for easy printing
pub fn linked_list_to_vec(head: Option<Rc<RefCell<ListNode>>>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut current = head;

    while let Some(node) = current {
        result.push(node.borrow().val);
        current = node.borrow_mut().next.take();
    }

    result
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_remove_nth_node() {
        // Test 1: [1, 2, 3, 4, 5], n=2
        let head1 = create_linked_list(vec![1, 2, 3, 4, 5]);
        let result1 = remove_nth_node_two_pointers(head1, 2);
        assert_eq!(linked_list_to_vec(result1), vec![1, 2, 3, 5]);

        // Test 2: [1], n=1
        let head2 = create_linked_list(vec![1]);
        let result2 = remove_nth_node_two_pointers(head2, 1);
        assert_eq!(linked_list_to_vec(result2), vec![]);

        // Test 3: [1, 2], n=2
        let head3 = create_linked_list(vec![1, 2]);
        let result3 = remove_nth_node_two_pointers(head3, 2);
        assert_eq!(linked_list_to_vec(result3), vec![2]);

        // Test 4: [1, 2], n=1
        let head4 = create_linked_list(vec![1, 2]);
        let result4 = remove_nth_node_two_pointers(head4, 1);
        assert_eq!(linked_list_to_vec(result4), vec![1]);
    }
}

Go

remove_nth_node_from_end_of_list_two_pointers.go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

/*
Remove the nth node from the end of a linked list using two pointers in one pass.

Approach:
1. Create a dummy node pointing to head (handles edge case of removing head)
2. Use fast and slow pointers with a gap of n nodes between them
3. Move both pointers until fast reaches the end
4. Skip the target node by adjusting the slow pointer

Time: O(L) single pass
Space: O(1)
*/
func removeNthNodeTwoPointers(head *ListNode, n int) *ListNode {
    // Create a dummy node to handle edge case of removing the head
    dummy := &ListNode{Val: 0}
    dummy.Next = head
    slow := dummy
    fast := dummy

    // Move fast pointer n+1 steps ahead
    for i := 0; i <= n; i++ {
        if fast == nil {
            return head
        }
        fast = fast.Next
    }

    // Move both pointers until fast reaches the end
    for fast != nil {
        slow = slow.Next
        fast = fast.Next
    }

    // Remove the nth node
    slow.Next = slow.Next.Next
    return dummy.Next
}

// Helper function to create a linked list from a slice
func createLinkedList(values []int) *ListNode {
    if len(values) == 0 {
        return nil
    }
    head := &ListNode{Val: values[0]}
    current := head
    for i := 1; i < len(values); i++ {
        current.Next = &ListNode{Val: values[i]}
        current = current.Next
    }
    return head
}

// Helper function to convert linked list to slice for easy printing
func linkedListToSlice(head *ListNode) []int {
    var result []int
    current := head
    for current != nil {
        result = append(result, current.Val)
        current = current.Next
    }
    return result
}

// Test cases
func main() {
    // Test 1: [1, 2, 3, 4, 5], n=2
    head1 := createLinkedList([]int{1, 2, 3, 4, 5})
    result1 := removeNthNodeTwoPointers(head1, 2)
    fmt.Println(linkedListToSlice(result1))  // [1 2 3 5]

    // Test 2: [1], n=1
    head2 := createLinkedList([]int{1})
    result2 := removeNthNodeTwoPointers(head2, 1)
    fmt.Println(linkedListToSlice(result2))  // []

    // Test 3: [1, 2], n=2
    head3 := createLinkedList([]int{1, 2})
    result3 := removeNthNodeTwoPointers(head3, 2)
    fmt.Println(linkedListToSlice(result3))  // [2]

    // Test 4: [1, 2], n=1
    head4 := createLinkedList([]int{1, 2})
    result4 := removeNthNodeTwoPointers(head4, 1)
    fmt.Println(linkedListToSlice(result4))  // [1]
}

Interactive Visualization

Animated walkthrough

Two-pointer gap maintains the distance to the target

Watch how the fast and slow pointers maintain a gap of exactly n nodes. When fast reaches the end, slow is perfectly positioned to remove the target node.

Back Autoplay Next Reset

Step 1 of 4 Target: gap

Waiting to begin...

Array state

Memory / lookup state

Approach 3: Optimized Two-Pointer

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

remove_nth_node_from_end_of_list_optimized.py

"""
Solution for Remove Nth Node From End of List
"""

def solve():
    """Implementation for approach 3 of Remove Nth Node From End of List"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

remove_nth_node_from_end_of_list_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Remove Nth Node From End of List
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

RemoveNthNodeFromEndOfListOptimized.java

/**
 * Solution for Remove Nth Node From End of List
 * Approach 3
 */
public class RemoveNthNodeFromEndOfListOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

remove_nth_node_from_end_of_list_optimized.js

/**
 * Solution for Remove Nth Node From End of List
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

remove_nth_node_from_end_of_list_optimized.rs

/// Solution for Remove Nth Node From End of List
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

remove_nth_node_from_end_of_list_optimized.go

package main

import "fmt"

// Solution for Remove Nth Node From End of List
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Not handling the head removal case — if n equals the list length, you must return head.next, not attempt to navigate before it.
• Off-by-one errors in the loop — forgetting to move to length - n - 1 instead of length - n in the two-pass approach.
• Not using a dummy node — the dummy node elegantly avoids the head case without extra branching; omitting it often leads to bugs.
• Breaking the loop early — in the two-pointer approach, iterating n times instead of n+1 times will misalign the pointers.
• Null pointer dereferences — always check that the node and its next pointer exist before accessing them.

Interview Tips

Key trade-offs to discuss

• Why two pointers over two pass? The single-pass solution is more elegant and shows mastery of pointer manipulation. Interviewers often explicitly ask for one-pass solutions.
• Why the dummy node? It eliminates the need for a special case when removing the head. Discuss how dummy nodes simplify edge cases in linked list operations.
• Gap maintenance: The key insight is that by moving fast n+1 steps ahead, we naturally create a gap of exactly n nodes. This gap is preserved as both pointers move together.
• Edge cases to mention: single-node lists, removing the head, removing the tail, and very small lists (n=1, length=1 vs. length=2).
• Follow-up — General Node Removal: Can extend to remove all occurrences of a value, or remove every kth node. The dummy node pattern is reusable.

Related Problems

• Merge Two Sorted Lists ↗ Easy #21
• Swap Nodes in Pairs ↗ Medium #24
• Rotate List ↗ Medium #61
• Remove Duplicates from Sorted List II ↗ Medium #82
• 4Sum ↗ Medium #18
• Valid Parentheses ↗ Easy #20

← Previous
#18 4Sum Next
#20 Valid Parentheses →