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