Kth Node From End - C++ Solution

1. Introduction

In this blog post, we'll explore a common problem in linked list manipulation: finding the k'th node from the end of the list. This problem is a good test of understanding two-pointer techniques in linked list traversal.

Problem

Given a non-empty linked list and a positive integer k, the task is to return the value of the k'th node from the end of the list.

Example:

Input: List = 1 —> 2 —> 3 —> 4 —> 5 —> nullptr, k = 3

Output: 3

Assumption: k is less than or equal to the number of nodes in the linked list.

2. Solution Steps

1. Use two pointers: fast and slow. Both initially point to the head of the list.

2. Move fast k nodes ahead in the list.

3. Move both fast and slow until fast reaches the end of the list.

4. At this point, slow will be pointing to the k'th node from the end.

3. Code Program

#include <iostream>
using namespace std;

// Define the ListNode structure
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to find the k'th node from the end
int kthFromEnd(ListNode* head, int k) {
    ListNode *fast = head, *slow = head;

    // Move fast k nodes ahead
    for (int i = 0; i < k; i++) {
        fast = fast->next;
    }

    // Move both pointers until fast reaches the end
    while (fast != nullptr) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow->val;
}

// Function to print the linked list
void printLinkedList(ListNode* head) {
    while (head) {
        cout << head->val << " —> ";
        head = head->next;
    }
    cout << "nullptr\n";
}

int main() {
    // Creating a linked list
    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);

    int k = 3;
    cout << "The " << k << "th node from the end is: " << kthFromEnd(head, k) << endl;
    return 0;
}

Output:

The 3th node from the end is: 3

Explanation:

The kthFromEnd function employs a two-pointer approach to find the k'th node from the end of the list. It first advances the fast pointer k nodes ahead. Then it moves both fast and slow pointers until fast reaches the end of the list. At this point, slow points to the k'th node from the end. The function returns the value of the node at the slow pointer. This approach efficiently finds the desired node in a single pass through the list.