এই সমস্যায়, আমাদের একটি লিঙ্ক-তালিকা এবং একটি সংখ্যা k দেওয়া হয়। আমাদের কাজ হল মিডল থেকে একটি লিঙ্কড লিস্টের প্রধানের দিকে kth নোড খুঁজে বের করা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট: লিঙ্কযুক্ত তালিকা :4 -> 2 -> 7 -> 1 -> 9 -> 12 -> 8 -> 10 -> 5, k =2
আউটপুট: ৭
ব্যাখ্যা:
মধ্যবর্তী নোডের মান হল 9.
মাঝ থেকে মাথার দিকে 2য় নোড হল 7৷
সমাধান পদ্ধতি
আমাদের লিঙ্কড-লিস্টের মাঝখান থেকে শুরুর দিকে kth উপাদান খুঁজে বের করতে হবে। এর জন্য আমাদের লিঙ্কড-লিস্টের সাইজ খুঁজে বের করতে হবে লিংকড-লিস্ট শুরু থেকে শেষ পর্যন্ত এবং সাইজ খুঁজে বের করার মাধ্যমে।
মাঝখান থেকে শুরুর দিকে K উপাদান হল শুরু থেকে (n/2 + 1 - k)তম উপাদান।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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);
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;
}
}
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
