Find the Nth Node from the End of a Linked List in C++

This C++ program demonstrates how to find the nth node from the end of a linked list using the two-pointer (or fast and slow pointer) technique, which is efficient and only requires a single pass through the list.

Program Code

#include <iostream>

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

// Function to find the nth node from the end of a linked list
ListNode* findNthFromEnd(ListNode* head, int n) {
    ListNode *fast = head, *slow = head;

    // Move fast pointer n steps ahead
    for (int i = 0; i < n; i++) {
        if (fast == NULL) return NULL;  // n is larger than the number of nodes in the list
        fast = fast->next;
    }

    // Move fast to the end, maintaining the gap
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }

    return slow;
}

// Helper function to print the linked list
void printList(ListNode* node) {
    while (node != NULL) {
        std::cout << node->val << " ";
        node = node->next;
    }
    std::cout << std::endl;
}

int main() {
    // Create a linked list: 1->2->3->4->5
    ListNode* a = new ListNode(1);
    a->next = new ListNode(2);
    a->next->next = new ListNode(3);
    a->next->next->next = new ListNode(4);
    a->next->next->next->next = new ListNode(5);

    // Find the 2nd node from the end
    ListNode* result = findNthFromEnd(a, 2);
    if (result != NULL) {
        std::cout << "The 2nd node from the end is: " << result->val << std::endl;
    } else {
        std::cout << "Invalid position!" << std::endl;
    }

    return 0;
}

Explanation of the Code

The program starts by defining a struct for the singly-linked list node. The main functionality is encapsulated in the findNthFromEnd function, which uses two pointers: fast and slow. The fast pointer advances n steps ahead of the slow pointer. Once the fast pointer is n steps ahead, both pointers advance at the same rate until the fast pointer reaches the end of the list. At this point, the slow pointer will be at the nth node from the end.

This two-pointer method is efficient as it traverses the list only once, and it is particularly useful in situations where the list size is unknown or the list is too long to traverse multiple times.

Conclusion

This program effectively demonstrates a common technique for solving problems related to linked lists, making it a useful snippet for many C++ developers working with data structures.