C++ Program to Find the Nth Node From the End of a Linked List

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* first = head;  // This pointer advances 'n' nodes ahead of the second pointer
    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* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);
    Node* fourth = new Node(4);

    // Link nodes together to form the linked list
    head->next = second;
    second->next = third;
    third->next = fourth;

    int n = 2;
    // Get the Nth node from the end
    Node* result = findNthFromEnd(head, n);

    // 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;
    delete head;

    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* first = head;  // This pointer advances 'n' nodes ahead of the second pointer
    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* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);
    Node* fourth = new Node(4);

    // Link nodes together to form the linked list
    head->next = second;
    second->next = third;
    third->next = fourth;

    int n = 2;
    // Get the Nth node from the end
    Node* result = findNthFromEnd(head, n);

    // 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;
    delete head;

    return 0;
}