C++ का उपयोग करके दिए गए सिंगली लिंक्ड लिस्ट में अंत से Kवां नोड खोजें

एक लिंक्ड लिस्ट एक रैखिक डेटा संरचना है जिसमें कई नोड्स होते हैं जो एक दूसरे से जुड़े होते हैं। प्रत्येक नोड में दो फील्ड होते हैं डेटा फील्ड और अगले नोड का पता। मान लीजिए हमारे पास एक सिंगली लिंक्ड लिस्ट दी गई है, कार्य दिए गए सिंगली लिंक्ड लिस्ट में अंत से Kवां नोड ढूंढना है। उदाहरण के लिए,

इनपुट -

1→2→3→4→7→8→9 K = 4

आउटपुट -

अंत से 4वीं पोजीशन का नोड है - 4

व्याख्या - चूंकि दी गई सिंगली लिंक्ड लिस्ट में अंत से '4वां' नोड '4' है, हम आउटपुट के रूप में '4' लौटाएंगे।

इस प्रॉब्लम को हल करने का दृष्टिकोण

प्रारंभ में, हमारे पास एक लिंक्ड लिस्ट है जिसमें नोड्स होते हैं। प्रत्येक नोड में डेटा और अगले नोड का पता होता है। इसलिए, अंत से kवां नोड ढूंढने के लिए, हम दो पॉइंटर्स लेंगे जो प्रारंभ में लिंक्ड लिस्ट के हेड की ओर इशारा करते हैं।

लिंक्ड लिस्ट पर पुनरावृति करते समय, हम पॉइंटर्स में से एक को आगे बढ़ाएंगे मान लीजिए 'फास्ट', और फिर दूसरे पॉइंटर को तब तक आगे बढ़ाएंगे जब तक 'फास्ट' पॉइंटर अंत तक नहीं पहुंच जाता।

• एक फंक्शन kthNodeFromTheEnd(node* head, int pos) हेड नोड का पॉइंटर और पोजीशन को पैरामीटर के रूप में लेता है और अंत से नोड लौटाता है।

• आइए दो पॉइंटर्स 'स्लो' और 'फास्ट' लें जो प्रारंभ में हेड पर हैं।

• लिंक्ड लिस्ट पर पुनरावृति करें और फास्ट पॉइंटर को आगे बढ़ाएं।

• चूंकि 'फास्ट' पॉइंटर 'स्लो' से दो कदम आगे है, आइए दोनों पॉइंटर्स को तब तक आगे बढ़ाएं जब तक 'फास्ट' अंत तक नहीं पहुंच जाता।

• अब स्लो पर मान लौटाएं जो अंत से kवें नोड की ओर इशारा करता है।

उदाहरण

#include <iostream>
using namespace std;

class node {
public:
    int data;
    node* next;
    node(int d) {
        data = d;
        next = NULL;
    }
};

void insertAtHead(node*& head, int d) {
    node* n = new node(d);
    n->next = head;
    head = n;
}

void printList(node* head) {
    while (head != NULL) {
        cout << head->data << "-->";
        head = head->next;
    }
}

void kthFromTheEnd(node* head, int k) {
    node* slow = head;
    node* fast = head;
    for (int i = 0; i < k; i++) {
        fast = fast->next;
    }
    while (fast != NULL) {
        slow = slow->next;
        fast = fast->next;
    }
    cout << "Node from the " << k << "th position is " << slow->data << endl;
}

int main() {
    node* head = NULL;
    insertAtHead(head, 2);
    insertAtHead(head, 4);
    insertAtHead(head, 5);
    insertAtHead(head, 6);
    insertAtHead(head, 7);
    printList(head);
    cout << endl;
    kthFromTheEnd(head, 4);
    return 0;
}

आउटपुट

उपरोक्त कोड चलाने पर निम्न आउटपुट उत्पन्न होगा,

अंत से 4वीं पोजीशन का नोड है: 6

व्याख्या - दी गई लिंक्ड लिस्ट 7→6→5→4→2→ है और k मान '4' है। तो, अंत से 4वां नोड '6' है, इस प्रकार हम '6' लौटाएंगे।