এই আর্টিকেলে, আমরা লিংকড লিস্ট থেকে প্রতি kth নোড বাদ দেওয়ার পদ্ধতি ব্যাখ্যা করব। আমাদের}k-র গুণিতক ওপর বসে যেসব নোড সেগুলো ডিলিট করতে হবে, অর্থাৎ k, 2*k, 3*k ইত্যাদি পজিশনের নোড ডিলিট করতে হবে।
ইনপুট : 112→231→31→41→54→63→71→85, k = 3 আউটপুট : 112→231→41→54→71→85 ব্যাখ্যা: ৩ হল kth নোড, এর ডিলিশনের পর লিস্ট হবে: প্রথম ইটারেশন: 112→231→41→54→63→71→85 এখন ৪১ থেকে কাউন্ট করলে পরবর্তী kth নোড হল ৬৩ দ্বিতীয় ইটারেশনের পর লিস্ট হবে: 112→231→41→54→71→85 এভাবে ইটারেশন চলবে। ইনপুট: 14→21→23→54→56→61, k = 1 আউটপুট: Empty list ব্যাখ্যা: সব নোড ডিলিট করতে হবে
এই সমস্যায়, আমরা একটি নরমাল পদ্ধতি প্রয়োগ করব যা অপ্টিমাইজেশন ছাড়াও যথেষ্ট দক্ষ।
সমাধানের পদ্ধতি
এই সমস্যায়, আমরা একটি কাউন্টার দিয়ে লিংকড লিস্ট ট্রাভার্স করব। যদি কাউন্টার k-এ পৌঁছায়, আমরা সেই নোডটি ডিলিট করব এবং পরবর্তী kth পজিশনের এলিমেন্ট খুঁজে বের করার জন্য কাউন্টার রিফ্রেশ করব।
উদাহরণ প্রোগ্রাম
#include<bits/stdc++.h>
using namespace std;
/* লিংকড লিস্ট নোড */
struct Node {
int data;
struct Node* next;
};
void push(struct Node** ref, int new_data) { // লিস্টে ডেটা পুশ করা
struct Node* new_n = new Node;
new_n->data = new_data;
new_n->next = (*ref);
(*ref) = new_n;
}
void deletek(Node* prev, Node* curr) { // ডিলিট ফাংশন
if (prev == NULL) {
prev = curr;
curr = curr->next;
free(prev);
prev = NULL;
} else {
prev->next = curr->next;
auto tmp = curr;
free(tmp); // স্পেস ফ্রি করা
}
}
/* লিংকড লিস্ট প্রিন্ট করার ফাংশন */
void displayList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
// নতুন নোড তৈরি করার ফাংশন
struct Node* newNode(int x) {
Node* temp = new Node;
temp->data = x;
temp->next = NULL;
return temp;
}
int main() {
struct Node* head = NULL;
push(&head, 80);
push(&head, 70);
push(&head, 60);
push(&head, 50);
push(&head, 40);
push(&head, 30);
push(&head, 20);
int k = 3; // দেয়া k
Node* curr = head; // কারেন্ট পয়েন্টার
Node* prev = NULL; // প্রিভিয়াস পয়েন্টার
int count = 1; // পজিশন কাউন্টার
if (head == NULL || k == 0) // যদি লিস্ট ইতিমধ্যে খালি থাকে বা k = 0
cout << "Invalid\n";
else {
while (curr) { // লিস্ট ট্রাভার্স করা
if (count == k) {
deletek(prev, curr);
curr = prev->next;
count = 1;
} else {
count++;
prev = curr;
curr = curr->next;
}
}
displayList(head); // নতুন লিস্ট প্রিন্ট করা
}
return 0;
}
আউটপুট
20 30 50 60 80
উপরোক্ত পদ্ধতির টাইম কমপ্লেক্সিটি O(N), যেখানে N হল আমাদের দেয়া লিংকড লিস্টের আকার।
উপরোক্ত কোডের ব্যাখ্যা
উপরোক্ত পদ্ধতিতে, আমরা তিনটি জিনিস হাতে রাখি: প্রথম, কারেন্ট পয়েন্টার, দ্বিতীয়, প্রিভিয়াস পয়েন্টার, এবং তৃতীয়, পজিশন কাউন্টার। এখন যখন আমাদের পজিশন কাউন্টার k-র সমান হয়ে যায়, আমরা ডিলিট ফাংশন কল করি প্রিভিয়াস এবং কারেন্ট কাউন্টার প্যারামিটার হিসেবে দিয়ে। এখন আমরা কারেন্ট নোড ডিলিট করি এবং স্পেস ফ্রি করি। এখন ডিলিট ফাংশন হলে, আমরা কারেন্ট পয়েন্টারকে নেক্স্ট এলিমেন্টে শিফট করি এবং আমাদের কাউন্টার ১-এ রিফ্রেশ করি এবং এই ব্লক লুপ করি যতক্ষণ না কারেন্ট NULL হয়।
উপসংহার
এই আর্টিকেলে, আমরা লিংকড লিস্ট থেকে প্রতি kth নোড বাদ দেওয়ার সমস্যা সমাধান করেছি। আমরা এই সমস্যায় C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (নরমাল) শিখেছি যেগুলো দিয়ে আমরা এই সমস্যা সমাধান করেছি। আমরা একই প্রোগ্রাম অন্যান্য ল্যাঙ্গুয়েজে লিখতে পারি যেমন C, Java, Python এবং অন্যান্য ল্যাঙ্গুয়েজ। আশা করি আপনি এই আর্টিকেলটিকে সহায়ক খুঁজে পাবেন।
