একটি সিঙ্গলি লিঙ্কড লিস্ট ও ধনাত্মক পূর্ণসংখ্যা N দেওয়া থাকলে, লিস্টের শেষ থেকে N-তম নোডটি রিকারসিভভাবে খুঁজে বের করতে হবে।
যেমন: লিস্ট = a → b → c → d → e → f এবং N = 4 হলে, শেষ থেকে ৪র্থ নোড হবে c।
বিভিন্ন ইনপুট-আউটপুট পরিস্থিতি
ইনপুট − লিস্ট: 1 → 5 → 7 → 12 → 2 → 96 → 33, N = 3
আউটপুট − শেষ থেকে N-তম নোড: 2
ব্যাখ্যা − ৩রা শেষ নোডটি ২।
ইনপুট − লিস্ট: 12 → 53 → 8 → 19 → 20 → 96 → 33, N = 8
আউটপুট − নোডটি বিদ্যমান নয়।
ব্যাখ্যা − লিস্টে মাত্র ৭টি নোড আছে, তাই ৮ম শেষ নোড সম্ভব নয়।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
রিকারসন দিয়ে লিস্টের শেষ পর্যন্ত যাওয়া হয়, তারপর ব্যাকট্র্যাকিং করার সময় একটি স্ট্যাটিক কাউন্টার বাড়ানো হয়। কাউন্ট N-এর সমান হলে বর্তমান নোডের পয়েন্টার ফেরত দেওয়া হয়।
Nodeস্ট্রাকচার:int dataওNode* next।addtohead(Node** head, int data)ফাংশন দিয়ে হেডে নোড যোগ করুন।display(Node* head)ফাংশন দিয়ে লিস্ট প্রিন্ট করুন।N ইনপুট নিন।
findNode(Node* head, int n1)ফাংশন ফলাফল প্রিন্ট করে।searchNthLast(Node* head, int n1, Node** nlast)ফাংশন রিকারসিভভাবে নোড খুঁজে বের করে।স্ট্যাটিক
countভেরিয়েবল ব্যবহার করুন।যদি
head == NULLহয়, তবে ফেরত যান।tmp = head->nextকরে রিকারসিভ কল দিন।ব্যাকট্র্যাকিং-এ
count++করুন।যদি
count == 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
