#include <iostream>
class Node {
public:
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
Node nthNodeFromEnd(Node head, int n) {
if (head == nullptr || n <= 0) {
return nullptr;
}
Node* slow = head;
Node* fast = head;
for (int i = 0; i < n; ++i) {
if (fast == nullptr) {
return nullptr; // List has fewer than n nodes
}
fast = fast->next;
}
while (fast != nullptr) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
int main() {
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(5);
int n = 2;
Node* result = nthNodeFromEnd(head, n);
if (result != nullptr) {
std::cout << "The " << n << "th node from the end is: " << result->data << std::endl;
} else {
std::cout << "Invalid input or list has fewer than " << n << " nodes." << std::endl;
}
// Clean up
while (head != nullptr) {
Node* temp = head;
head = head->next;
delete temp;
}
return 0;
}