একটি লিঙ্ক করা তালিকা হল একটি লিনিয়ার ডেটা স্ট্রাকচার যাতে একাধিক নোড থাকে যা একে অপরের সাথে সংযুক্ত থাকে। প্রতিটি নোড দুটি ক্ষেত্র ডেটা ফিল্ড এবং পরবর্তী নোডের ঠিকানা নিয়ে গঠিত। ধরা যাক আমরা একটি এককভাবে লিঙ্কযুক্ত তালিকা দিয়েছি কাজটি হল একটি প্রদত্ত একক লিঙ্কযুক্ত তালিকার শেষ থেকে kth নোড খুঁজে বের করা। উদাহরণস্বরূপ,
ইনপুট −
1→2→3→4→7→8→9 K= 4
আউটপুট −
Node from the 4th Position is − 4
ব্যাখ্যা − যেহেতু প্রদত্ত এককভাবে লিঙ্ক করা তালিকায় '4র্থ' নোডটি শেষ থেকে '4', তাই আমরা আউটপুটটি '4' হিসাবে ফেরত দেব।
এই সমস্যা সমাধানের পদ্ধতি
প্রাথমিকভাবে, আমরা একটি লিঙ্কযুক্ত তালিকা দিয়েছি যা নোড নিয়ে গঠিত। প্রতিটি নোডে পরবর্তী নোডের ডেটা এবং ঠিকানা থাকে। সুতরাং, শেষ থেকে kth নোড খুঁজে পেতে, আমরা দুটি পয়েন্টার নেব যা প্রাথমিকভাবে লিঙ্ক করা তালিকার প্রধানের দিকে নির্দেশ করে।
লিঙ্ক করা তালিকার উপর পুনরাবৃত্তি করার সময়, আমরা একটি পয়েন্টার সরাব যা বলা যাক 'দ্রুত', এবং তারপরে 'দ্রুত' পয়েন্টারটি শেষ না হওয়া পর্যন্ত অন্য পয়েন্টারটি সরাতে হবে।
-
একটি ফাংশন kthNodefromTheEnd(node*head, int pos) পয়েন্টারটিকে হেড নোডে এবং একটি প্যারামিটার হিসাবে অবস্থানে নিয়ে যায় এবং শেষ থেকে নোডটি ফেরত দেয়।
-
আসুন দুটি পয়েন্টার নিই 'ধীর' এবং 'দ্রুত' যা প্রাথমিকভাবে মাথায় থাকে।
-
লিঙ্ক করা তালিকার উপর পুনরাবৃত্তি করুন এবং দ্রুত পয়েন্টার সরান।
-
যেহেতু 'দ্রুত' পয়েন্টারটি 'ধীর' থেকে দুই ধাপ এগিয়ে, আসুন 'দ্রুত' শেষ না হওয়া পর্যন্ত উভয় পয়েন্টারকে সরানো যাক।
-
এখন ধীর গতিতে মানটি ফেরত দিন যা শেষ থেকে kth নোডকে নির্দেশ করে।
উদাহরণ
#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;
} আউটপুট
উপরের কোডটি চালানোর ফলে আউটপুট তৈরি হবে,
Node from the 4th position is: 6
ব্যাখ্যা − প্রদত্ত লিঙ্কযুক্ত তালিকাটি হল 7→ 6→ 5→ 4→ 2→ এবং kth মান হল ‘4’। সুতরাং, শেষ থেকে 4র্থ নোড হল '6', এইভাবে আমরা '6' ফেরত দেব।
