इनपुट के रूप में सिंगल लिंक्ड लिस्ट और पॉजिटिव इंटीजर N को देखते हुए। लक्ष्य रिकर्सन का उपयोग करके दी गई सूची में अंत से एनएच नोड को ढूंढना है। यदि इनपुट सूची में नोड्स a → b → c → d → e → f और N 4 हैं तो अंत से चौथा नोड c होगा।
हम पहले सूची में अंतिम नोड तक जाएंगे और रिकर्सन (बैकट्रैकिंग) वृद्धि गणना से लौटते समय। जब गिनती एन के बराबर हो तो परिणाम के रूप में वर्तमान नोड पर पॉइंटर लौटाएं।
आइए इसके लिए विभिन्न इनपुट आउटपुट परिदृश्य देखें -
इनपुट - सूची :- 1 → 5 → 7 → 12 → 2 → 96 → 33 N=3
आउटपुट - अंतिम से वां नोड है:2
स्पष्टीकरण - तीसरा अंतिम नोड 2 है।
इनपुट - सूची :- 12 → 53 → 8 → 19 → 20 →96 → 33 N=8
आउटपुट -नोड मौजूद नहीं है।
स्पष्टीकरण - सूची में केवल 7 नोड हैं, इसलिए 8वां अंतिम नोड संभव नहीं होगा।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
इस दृष्टिकोण में हम पहले रिकर्सन का उपयोग करके सूची के अंत तक पहुंचेंगे और बैकट्रैकिंग करते समय हम एक स्थिर गणना चर बढ़ाएंगे। जैसे ही गिनती इनपुट एन के बराबर हो जाती है, वर्तमान नोड पॉइंटर वापस कर दें।
-
स्ट्रक्चर नोड को इंट डेटा पार्ट और नोड को अगले पॉइंटर के रूप में लें।
-
फ़ंक्शन addtohead (नोड ** हेड, इंट डेटा) का उपयोग एकल लिंक की गई सूची बनाने के लिए सिर में नोड्स जोड़ने के लिए किया जाता है।
-
पहले नोड के सूचक के रूप में शीर्ष के साथ उपरोक्त फ़ंक्शन का उपयोग करके एक एकल लिंक की गई सूची बनाएं।
-
फ़ंक्शन डिस्प्ले (नोड * हेड) का उपयोग हेड नोड से शुरू होने वाली लिंक की गई सूची को प्रिंट करने के लिए किया जाता है।
-
N को एक धनात्मक पूर्णांक के रूप में लें।
-
फ़ंक्शन फाइंडनोड (नोड * हेड, इंट एन 1) पॉइंटर को हेड और एन 1 पर ले जाता है और अंत से n1 वां नोड मिलने पर परिणाम प्रिंट करता है।
-
ब्लास्ट को अंत से n1वें नोड पर पॉइंटर के रूप में लें।
-
उस नोड को खोजने के लिए searchNthLast(head, n1, &nlast) पर कॉल करें।
-
फ़ंक्शन searchNthLast(Node* head, int n1, Node** nlast) पहले नोड के रूप में शीर्ष के साथ लिंक की गई सूची में अंत से n1वें अंतिम नोड पर पॉइंटर लौटाता है।
-
एक स्थिर गणना चर लें।
-
अगर सिर NULL है तो कुछ भी नहीं लौटाएं।
-
tmp=head->अगला लें।
-
अंतिम नोड तक पुनरावर्ती रूप से ट्रैवर्स करने के लिए searchNthLast(tmp, n1, nlast) को कॉल करें।
-
उसके बाद 1 से वेतन वृद्धि की गणना करें।
-
अगर गिनती n1 के बराबर हो जाती है तो *nlast=head सेट करें।
-
अंत में परिणाम के रूप में nlast द्वारा इंगित नोड का मान प्रिंट करें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
void addtohead(Node** head, int data){
Node* nodex = new Node;
nodex->data = data;
nodex->next = (*head);
(*head) = nodex;
}
void searchNthLast(Node* head, int n1, Node** nlast){
static int count=0;
if (head==NULL){
return;
}
Node* tmp=head->next;
searchNthLast(tmp, n1, nlast);
count = count + 1;
if (count == n1){
*nlast = head;
}
}
void findNode(Node* head, int n1){
Node* nlast = NULL;
searchNthLast(head, n1, &nlast);
if (nlast == NULL){
cout << "Node does not exists";
}
else{
cout << "Nth Node from the last is: "<< nlast->data;
}
}
void display(Node* head){
Node* curr = head;
if (curr != NULL){
cout<<curr->data<<" ";
display(curr->next);
}
}
int main(){
Node* head = NULL;
addtohead(&head, 20);
addtohead(&head, 12);
addtohead(&head, 15);
addtohead(&head, 8);
addtohead(&head, 10);
addtohead(&head, 4);
addtohead(&head, 5);
int N = 2;
cout<<"Linked list is :"<<endl;
display(head);
cout<<endl;
findNode(head, N);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा
Linked list is : 5 4 10 8 15 12 20 Nth Node from the last is: 12