1. Introduction

Finding the nth node from the end of a linked list is a common interview question and an essential operation when working with linked lists. This post dives into a C++ solution for this problem without having to traverse the linked list more than once.

2. Program Overview

The trick is to use two-pointers. We'll advance one pointer n nodes ahead first. Once the first pointer has moved n nodes, we'll start moving the second pointer. By the time the first pointer reaches the end of the linked list, the second pointer will be n nodes from the end.

3. Code Program

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

// Definition of a node in the linked list
class Node {
public:
int data;           // Value contained in the node
Node* next;         // Pointer to the next node in the list

// Constructor to initialize the node with a value and set next to nullptr
Node(int val) : data(val), next(nullptr) {}
};

// Function to find the Nth node from the end of the linked list
Node* findNthFromEnd(Node* head, int n) {
Node* second = head; // This pointer starts at the beginning

// Move 'first' n nodes ahead in the list
for (int i = 0; i < n; i++) {
if (!first) return nullptr;  // If list has less than 'n' nodes
first = first->next;
}

// Traverse the rest of the list. When 'first' reaches the end, 'second' will be at (length - n)th node.
while (first) {
first = first->next;
second = second->next;
}

return second; // This will be the Nth node from the end
}

int main() {
// Create nodes for the linked list
Node* second = new Node(2);
Node* third = new Node(3);
Node* fourth = new Node(4);

second->next = third;
third->next = fourth;

int n = 2;
// Get the Nth node from the end

// Print the result
if(result) {
cout << "The " << n << "th node from the end is: " << result->data << endl;
} else {
cout << "List is shorter than " << n << " nodes." << endl;
}

// Clean up memory by deleting nodes
delete fourth;
delete third;
delete second;

return 0;
}
``````

Output:

```The 2th node from the end is: 3
```

4. Step By Step Explanation

1. The Node class represents a node in our linked list.

``````// Definition of a node in the linked list
class Node {
public:
int data;           // Value contained in the node
Node* next;         // Pointer to the next node in the list

// Constructor to initialize the node with a value and set next to nullptr
Node(int val) : data(val), next(nullptr) {}
};``````

2. The function findNthFromEnd identifies the nth node from the end using the two-pointer method as explained above.

``````// Function to find the Nth node from the end of the linked list
Node* findNthFromEnd(Node* head, int n) {
Node* second = head; // This pointer starts at the beginning

// Move 'first' n nodes ahead in the list
for (int i = 0; i < n; i++) {
if (!first) return nullptr;  // If list has less than 'n' nodes
first = first->next;
}

// Traverse the rest of the list. When 'first' reaches the end, 'second' will be at (length - n)th node.
while (first) {
first = first->next;
second = second->next;
}

return second; // This will be the Nth node from the end
}``````

2. In the main function, we've constructed a linked list with four nodes and then called our function to find the 2nd node from the end, which is 3 in this case. Proper memory management practices are followed by deallocating the nodes after usage.

``````int main() {
// Create nodes for the linked list
Node* second = new Node(2);
Node* third = new Node(3);
Node* fourth = new Node(4);

second->next = third;
third->next = fourth;

int n = 2;
// Get the Nth node from the end

// Print the result
if(result) {
cout << "The " << n << "th node from the end is: " << result->data << endl;
} else {
cout << "List is shorter than " << n << " nodes." << endl;
}

// Clean up memory by deleting nodes
delete fourth;
delete third;
delete second;