एक लिंक्ड सूची एक रैखिक डेटा संरचना है जिसमें कई नोड्स होते हैं जो एक दूसरे से जुड़े होते हैं। प्रत्येक नोड में दो फ़ील्ड होते हैं डेटा फ़ील्ड और अगले नोड का पता। आइए मान लें कि हमने एक एकल लिंक की गई सूची दी है, कार्य किसी एकल लिंक की गई सूची में अंत से kth नोड को खोजने का है। उदाहरण के लिए,
इनपुट -
1→2→3→4→7→8→9 K= 4
आउटपुट -
Node from the 4th Position is − 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' है। तो, अंत से चौथा नोड '6' है, इस प्रकार हम '6' वापस करेंगे।