#include <iostream>
#include <vector>

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

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

        // Move first n+1 steps ahead
        for (int i = 0; i <= n; ++i) {
            first = first->next;
        }

        // Move first to the end, maintaining the gap
        while (first != nullptr) {
            first = first->next;
            second = second->next;
        }

        // Skip the desired node
        second->next = second->next->next;

        return dummy.next;
    }
};


ListNode* vectorToList(const std::vector<int>& values) {
    if (values.empty()) return nullptr;
    ListNode* head = new ListNode(values[0]);
    ListNode* current = head;
    for (size_t i = 1; i < values.size(); ++i) {
        current->next = new ListNode(values[i]);
        current = current->next;
    }
    return head;
}

std::vector<int> listToVector(ListNode* head) {
    std::vector<int> result;
    while (head != nullptr) {
        result.push_back(head->val);
        head = head->next;
    }
    return result;
}

void printList(ListNode* head) {
    while (head != nullptr) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

void testRemoveNthFromEnd() {
    Solution solution;

    // Test case 1
    ListNode* head1 = vectorToList({1, 2, 3, 4, 5});
    ListNode* result1 = solution.removeNthFromEnd(head1, 2);
    std::vector<int> expected1 = {1, 2, 3, 5};
    std::vector<int> output1 = listToVector(result1);
    std::cout << "Test 1 " << (output1 == expected1 ? "passed" : "failed") << std::endl;

    // Test case 2
    ListNode* head2 = vectorToList({1});
    ListNode* result2 = solution.removeNthFromEnd(head2, 1);
    std::vector<int> expected2 = {};
    std::vector<int> output2 = listToVector(result2);
    std::cout << "Test 2 " << (output2 == expected2 ? "passed" : "failed") << std::endl;

    // Test case 3
    ListNode* head3 = vectorToList({1, 2});
    ListNode* result3 = solution.removeNthFromEnd(head3, 1);
    std::vector<int> expected3 = {1};
    std::vector<int> output3 = listToVector(result3);
    std::cout << "Test 3 " << (output3 == expected3 ? "passed" : "failed") << std::endl;

    // Additional Test case 4
    ListNode* head4 = vectorToList({1, 2, 3, 4, 5});
    ListNode* result4 = solution.removeNthFromEnd(head4, 5);
    std::vector<int> expected4 = {2, 3, 4, 5};
    std::vector<int> output4 = listToVector(result4);
    std::cout << "Test 4 " << (output4 == expected4 ? "passed" : "failed") << std::endl;

    // Additional Test case 5
    ListNode* head5 = vectorToList({1, 2, 3});
    ListNode* result5 = solution.removeNthFromEnd(head5, 3);
    std::vector<int> expected5 = {2, 3};
    std::vector<int> output5 = listToVector(result5);
    std::cout << "Test 5 " << (output5 == expected5 ? "passed" : "failed") << std::endl;
}

int main() {
    testRemoveNthFromEnd();
    return 0;
}