একটি সিংলি লিংকড লিস্ট এবং একটি সংখ্যা k দেওয়া আছে। লিস্টের মাঝপথের নোড থেকে হেড দিকের দিকে k-তম নোড বের করতে হবে।
উদাহরণ
লিস্ট: 4→2→7→1→9→12→8→10→5 (হেড=৪, টেল=৫)
k = 2
মাঝপথ নোড (৯, ইনডেক্স ৪, ০-বেসড)। মাঝপথ থেকে ২ ধাপ হেড দিক → ইনডেক্স ২ → মান 7।
আউটপুট: 7
অ্যালগরিদম
- লিস্ট ট্রাভার্স করে সাইজ
nবের করুন। - মাঝপথ ইনডেক্স (১-বেসড) =
n/2 + 1। - হেড থেকে টার্গেট ইনডেক্স =
midIdx - k। - হেড থেকে সে ইনডেক্স পর্যন্ত ট্রাভার্স করুন।
C++ প্রোগ্রাম
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void pushNode(struct Node** head_ref, int new_data) {
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int findKmiddleNode(struct Node* head_ref, int k) {
int n = 0;
struct Node* counter = head_ref;
while (counter != NULL) {
n++;
counter = counter->next;
}
int reqNode = (n / 2 + 1) - k; // 1-based
if (reqNode <= 0) return -1;
struct Node* current = head_ref;
int count = 1;
while (current != NULL) {
if (count == reqNode) return current->data;
count++;
current = current->next;
}
return -1;
}
int main() {
struct Node* head = NULL;
int k = 2;
pushNode(&head, 5);
pushNode(&head, 10);
pushNode(&head, 8);
pushNode(&head, 12);
pushNode(&head, 9);
pushNode(&head, 1);
pushNode(&head, 7);
pushNode(&head, 2);
pushNode(&head, 4);
cout << k << "th element from beginning towards head is " << findKmiddleNode(head, k);
return 0;
}
আউটপুট
2th element from beginning towards head is 7
ব্যাখ্যা
pushNodeহেডে ইনসার্ট করে → লিস্ট বিল্ড হয় রিভার্স অর্ডারে।n=9→ মাঝপথ = ৫ম নোড (১-বেসড) = মান ৯।reqNode = 5 - 2 = 3→ ৩য় নোড = ৭।- টাইম:
O(n)(দুই পাস), স্পেস:O(1)।
ওয়ান-পাস (স্লো/ফাস্ট পয়েন্টার)
স্লো/ফাস্ট দিয়ে মাঝপথ খুঁজে, তারপর k ধাপ পিছিয়ে যাওয়া যায় কিন্তু সিংলি লিস্টে পিছিয়ে যাওয়া যাবে না। তাই টু-পাসই সহজ।
