এই নিবন্ধে, আমরা লিঙ্ক করা তালিকার প্রতিটি k-th নোড সরানোর উপায় ব্যাখ্যা করব। আমাদের অবশ্যই k এর মাল্টিপল-এ বসে থাকা প্রতিটি নোড মুছে ফেলতে হবে, অর্থাৎ, k, 2*k, 3*k, ইত্যাদি অবস্থানের নোড মুছতে হবে।
Input : 112->231->31->41->54->63->71->85 k = 3 Output : 112->231->41->54->71->85 Explanation: As 3 is the k-th node after its deletion list would be : First iteration :112->231->41->54->63->71->85 Now we count from 41 the next kth node is 63 After the second iteration our list will become : 112->231->41->54->71->85 And our iteration continues like this. Input: 14->21->23->54->56->61 k = 1 Output: Empty list Explanation: All nodes need to be deleted
এই সমস্যায়, আমরা একটি সাধারণ পদ্ধতি প্রয়োগ করব যা যথেষ্ট দক্ষ যাতে আমাদের এটিকে অপ্টিমাইজ করার প্রয়োজন না হয়৷
সমাধান খোঁজার পদ্ধতি
এই সমস্যায়, আমরা একটি কাউন্টারের সাথে লিঙ্কযুক্ত তালিকাটি অতিক্রম করতে যাচ্ছি। যদি কাউন্টার k তে আঘাত করে, আমরা সেই নোডটি মুছে ফেলি এবং বর্তমান নোড থেকে kth অবস্থানে পরবর্তী উপাদানটি খুঁজে পেতে কাউন্টারটিকে রিফ্রেশ করি।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
/* Linked list Node */
struct Node {
int data;
struct Node* next;
};
void push(struct Node** ref, int new_data) { // pushing the data into the list
struct Node* new_n = new Node;
new_n->data = new_data;
new_n->next = (*ref);
(*ref) = new_n;
}
void deletek(Node* prev, Node* curr) { // delete function
if(prev == NULL) {
prev = curr;
curr = curr -> next;
free(prev);
prev = NULL;
} else {
prev -> next = curr -> next;
auto tmp = curr;
free(tmp); // freeing the space
}
}
/* Function to print linked list */
void displayList(struct Node *head) {
struct Node *temp = head;
while (temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
}
// Function to create a new node.
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; // given k
Node* curr = head; // current pointer
Node* prev = NULL; // previous pointer
int count = 1; // position counter
if(head == NULL || k == 0) // if list is already empty or k = 0
cout << "Invalid\n";
else {
while(curr) { // traversing the list
if(count == k) {
deletek(prev, curr);
curr = prev -> next;
count = 1;
} else {
count++;
prev = curr;
curr = curr -> next;
}
}
displayList(head); // printing the new list
}
return 0;
} আউটপুট
20 30 50 60 80
উপরের পদ্ধতির O(N) এর একটি সময় জটিলতা রয়েছে , যেখানে N হল আমাদের প্রদত্ত লিঙ্ক করা তালিকার আকার।
উপরের কোডের ব্যাখ্যা
উপরের পদ্ধতিতে, আমরা প্রথমে তিনটি জিনিস হাতে রাখি, বর্তমান পয়েন্টার, দ্বিতীয়টি পূর্ববর্তী পয়েন্টার এবং তৃতীয় অবস্থান কাউন্টার। এখন আমরা কিছু নোড মুছে ফেলি যখন আমাদের অবস্থান কাউন্টার সমান হয়ে যায় তখন আমরা ফাংশনটিকে পূর্ববর্তী এবং বর্তমান কাউন্টার দিয়ে মুছে ফেলার জন্য প্যারামিটার হিসাবে কল করি এখন আমরা বর্তমান নোডটি মুছে ফেলি এবং এখন স্থান খালি করি যখন ডিলিট ফাংশনটি এখন আমরা বর্তমান পয়েন্টারকে স্থানান্তরিত করি পরবর্তী উপাদান এবং আমাদের কাউন্টার 1 এ রিফ্রেশ করুন এবং এই ব্লকটি লুপ করুন যতক্ষণ না আমাদের বর্তমান শূন্য হয়ে যায়।
উপসংহার
এই নিবন্ধে, আমরা লিঙ্ক করা তালিকার প্রতিটি k-th নোড সরানোর জন্য একটি সমস্যার সমাধান করি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই নিবন্ধটি সহায়ক হবে৷
