C++ में लिंक्ड लिस्ट के मध्य से हेड की ओर k-वां नोड ढूंढें

इस समस्या में, हमें एक लिंक्ड-लिस्ट और एक संख्या k दी गई है। हमारा कार्य लिंक्ड लिस्ट के मध्य से हेड की ओर k-वां नोड ढूंढना है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट: linked-list : 4 -> 2 -> 7 -> 1 -> 9 -> 12 -> 8 -> 10 -> 5, k = 2

आउटपुट: 7

व्याख्या:

मध्य नोड मान 9 है।

मध्य से हेड की ओर दूसरा नोड 7 है।

समाधान दृष्टिकोण

हमें लिंक्ड-लिस्ट के मध्य से शुरुआत की ओर k-वां तत्व ढूंढना है। इसके लिए हमें लिंक्ड-लिस्ट को शुरुआत से अंत तक ट्रैवर्स करके लिंक्ड-लिस्ट का आकार ढूंढना होगा।

मध्य से शुरुआत की ओर k तत्व, शुरुआत से (n/2 + 1 - k)वां तत्व है।

हमारे समाधान की कार्यप्रणाली को दर्शाने वाला प्रोग्राम,

उदाहरण

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node* next;
};

void pushNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int findKmiddleNode(struct Node* head_ref, int k) {
    int n = 0;
    struct Node* counter = head_ref;
    while (counter != NULL) {
        n++;
        counter = counter->next;
    }
    int reqNode = ((n / 2 + 1) - k);
    if (reqNode <= 0)
        return -1;
    struct Node* current = head_ref;
    int count = 1;
    while (current != NULL) {
        if (count == reqNode)
            return (current->data);
        count++;
        current = current->next;
    }
}

int main() {
    struct Node* head = NULL;
    int k = 2;
    pushNode(&head, 5);
    pushNode(&head, 10);
    pushNode(&head, 8);
    pushNode(&head, 12);
    pushNode(&head, 9);
    pushNode(&head, 1);
    pushNode(&head, 7);
    pushNode(&head, 2);
    pushNode(&head, 4);
    cout<<k<<"th element from beginning towards head is "<<findKmiddleNode(head, k);
    return 0;
}

आउटपुट

2th element from beginning towards head is 7