Problem Statement

Given a singly linked list and an integer n. Find the nth node from the end of the linked list and return its value.

If n is greater than the length of the list, return a message indicating that the position is out of bounds.

Examples

Example 1:

Input: List 1 -> 2 -> 3 -> 4 -> 5 -> nullptr, N = 2
Output: 4

Explanation: The second node from the last is 4 while 5 is the last node.

Example 2:

Input: List 1 -> 2 -> 3 -> 4 -> 5 -> nullptr, N = 5
Output: 1

Explanation: The fifth node from the last is 1.

Intuition

We can solve this problem using one of the derivation of Two-Pointers technique | pattern which is Lead and Lag pointers.

The lead and lag pointer technique involves using two pointers (often referred to as the "lead" and "lag" pointers):

1. Lead Pointer: This pointer will be moved n steps ahead in the linked list.
2. Lag Pointer: This pointer will start from the head and will move simultaneously with the lead pointer after the lead pointer has moved n steps.

• By moving the lead pointer n steps ahead first, the distance between the lead and lag pointers becomes n nodes.
• When the lead pointer reaches the end of the list, the lag pointer will be exactly n nodes behind it, hence pointing to the nth node from the end.

Approach

1. Initialize both pointers: Start with both pointers (lead and lag) at the head of the linked list.
2. Advance the lead pointer: Move the lead pointer n steps forward.
3. Check out-of-bounds: If the lead pointer reaches nullptr before completing n steps, then n is larger than the number of nodes in the list.
4. Move both pointers together: Move both pointers one step at a time until the lead pointer reaches the end of the list.
5. Output: The lag pointer will be pointing at the nth node from the end.

Code

#include <iostream>

struct ListNode {
    int data;
    ListNode* next;
    ListNode(int x) : data(x), next(nullptr) {}
};

// Function to find the nth node from the end of the linked list using lead and lag pointers
int findNthFromEnd(ListNode* head, int n) {
    ListNode* lead = head;  // Lead pointer
    ListNode* lag = head;   // Lag pointer

    // Step 1: Move the lead pointer n steps ahead
    for (int i = 0; i < n; ++i) {
        if (lead == nullptr) {
            std::cout << "Out of bounds" << std::endl;
            return -1; // Out of bounds
        }
        lead = lead->next;
    }

    // Step 2: Move both pointers until lead reaches the end
    while (lead != nullptr) {
        lead = lead->next;
        lag = lag->next;
    }

    // Step 3: The lag pointer is now pointing to the nth node from the end
    if (lag != nullptr) {
        return lag->data;
    } else {
        std::cout << "Out of bounds" << std::endl;
        return -1; // Out of bounds
    }
}

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

int main() {
    // Create a simple linked list with initial elements
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    std::cout << "Original list: ";
    printList(head);

    // Find the 2nd node from the end
    int n = 2;
    int result = findNthFromEnd(head, n);
    if (result != -1) {
        std::cout << "The " << n << "th node from the end is: " << result << std::endl;
    }

    // Find the 5th node from the end
    n = 5;
    result = findNthFromEnd(head, n);
    if (result != -1) {
        std::cout << "The " << n << "th node from the end is: " << result << std::endl;
    }

    // Find the 6th node from the end (Out of bounds)
    n = 6;
    result = findNthFromEnd(head, n);
    if (result != -1) {
        std::cout << "The " << n << "th node from the end is: " << result << std::endl;
    }

    return 0;
}

Complexity Analysis

• Time Complexity: O(n)
  • The function only traverses the list once. First, it moves the lead pointer n steps ahead, and then it moves both pointers until the lead pointer reaches the end. This results in a linear time complexity relative to the number of nodes (n) in the list.
• Space Complexity: O(1)
  • The solution uses a fixed amount of extra space (two pointers), so the space complexity is constant.