एक एकल लिंक्ड सूची और एक धनात्मक पूर्णांक N इनपुट के रूप में दिया गया है। लक्ष्य है दी गई सूची में अंत से Nवें नोड को पुनरावर्तन का उपयोग करके ढूंढना। यदि इनपुट सूची में नोड्स a → b → c → d → e → f हैं और N=4 है, तो अंत से 4था नोड c होगा।
हम पहले सूची के अंतिम नोड तक पुनरावर्तन से ट्रैवर्स करते हैं और बैकट्रैकिंग के दौरान एक काउंटर बढ़ाते हैं। जब काउंट N के बराबर हो जाता है, तो वर्तमान नोड का पॉइंटर परिणाम के रूप में लौटाते हैं।
विभिन्न इनपुट-आउटपुट परिदृश्य
इनपुट - सूची: 1 → 5 → 7 → 12 → 2 → 96 → 33, N=3
आउटपुट - अंत से Nवां नोड है: 2
व्याख्या - अंत से 3रा नोड 2 है।
इनपुट - सूची: 12 → 53 → 8 → 19 → 20 → 96 → 33, N=8
आउटपुट - नोड मौजूद नहीं है।
व्याख्या - सूची में केवल 7 नोड्स हैं इसलिए 8वां अंतिम नोड संभव नहीं है।
उपयोग किया गया दृष्टिकोण
इस दृष्टिकोण में हम पहले पुनरावर्तन का उपयोग करके सूची के अंत तक पहुंचते हैं और बैकट्रैकिंग के दौरान एक स्टैटिक काउंट वेरिएबल बढ़ाते हैं। जैसे ही काउंट इनपुट N के बराबर होता है, वर्तमान नोड पॉइंटर लौटाते हैं।
इंट डेटा पार्ट और Node नेक्स्ट पॉइंटर के साथ Node स्ट्रक्चर लें।
फ़ंक्शन addtohead(Node** head, int data) का उपयोग हेड पर नोड्स जोड़कर एकल लिंक्ड सूची बनाने के लिए किया जाता है।
उपरोक्त फ़ंक्शन का उपयोग करके हेड को पहले नोड के पॉइंटर के रूप में एकल लिंक्ड सूची बनाएं।
फ़ंक्शन display(Node* head) का उपयोग हेड नोड से शुरू करके लिंक्ड सूची प्रिंट करने के लिए किया जाता है।
N को एक धनात्मक पूर्णांक के रूप में लें।
फ़ंक्शन findNode(Node* head, int n1) हेड का पॉइंटर और n1 लेता है और जब अंत से n1वां नोड मिल जाता है तो परिणाम प्रिंट करता है।
अंत से n1वें नोड के पॉइंटर के रूप में nlast लें।
उस नोड को ढूंढने के लिए searchNthLast(head, n1, &nlast) कॉल करें।
फ़ंक्शन searchNthLast(Node* head, int n1, Node** nlast) हेड को पहले नोड के रूप में लिंक्ड सूची में अंत से n1वें नोड का पॉइंटर लौटाता है।
एक स्टैटिक काउंट वेरिएबल लें।
यदि head NULL है तो कुछ भी वापस न करें।
tmp = head->next लें।
अंतिम नोड तक पुनरावर्ती रूप से ट्रैवर्स करने के लिए 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