একটি লিঙ্কড লিস্ট A এবং পূর্ণসংখ্যা K দেওয়া আছে। K আকারের 얼্টারনেট জোড়া নোড রিভার্স করতে হবে। N, K-র গুণিতক।
ইনপুট/আউটপুট উদাহরণ
ইনপুট: 5→6→2→8→5→2→4→8→9→6→NULL, K=2
আউটপুট: 6→5→2→8→2→5→4→8→6→9→NULL
ইনপুট: 1→2→5→8→9→6→4→5→8→NULL, K=3
আউটপুট: 5→2→1→8→9→6→8→5→4→NULL
সমাধানের পদ্ধতি
ইটারেটিভ সমাধান
- প্রতি ইটারেশনে 2K নোড ট্রাভার্স করুন
- প্রতিটি K নোডের জোড়ার হেড ও টেইল রেকর্ড করুন
- প্রথম K নোড রিভার্স করুন, টেইলকে জয়েন করুন
- পরবর্তী K নোড স্কিপ করুন
- প্রক্রিয়া পুনরাবৃত্তি করুন
উদাহরণ ১ (ইটারেটিভ)
#include <bits/stdc++.h>
using namespace std;
class Node { public: int data; Node* next; };
Node* kAltReverse(Node* head, int k) {
Node *prev = NULL, *curr = head, *temp = NULL;
Node *tail = NULL, *newHead = NULL, *join = NULL;
int t = 0;
while (curr) {
t = k; join = curr; prev = NULL;
while (curr && t--) {
temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
if (!newHead) newHead = prev;
if (tail) tail->next = prev;
tail = join;
tail->next = curr;
t = k;
while (curr && t--) {
prev = curr;
curr = curr->next;
}
tail = prev;
}
return newHead;
}
void push(Node** head_ref, int new_data) {
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
void printList(Node* node) {
while (node) { cout << node->data << " "; node = node->next; }
}
int main() {
Node* head = NULL;
for (int i = 24; i >= 6; i -= 3) push(&head, i);
int k = 3;
cout << "Given linked list \n"; printList(head);
head = kAltReverse(head, k);
cout << "\nModified Linked list \n"; printList(head);
return 0;
}
আউটপুট
Given linked list: 24 21 18 15 12 9 6 Modified Linked list: 18 21 24 15 12 9 6
রিকার্সিভ সমাধান
K নোড ট্রাভার্স করে রিভার্স করুন, পরবর্তী K নোড স্কিপ করুন, রিকার্সিভভাবে একই কাজ করুন।
উদাহরণ ২ (রিকার্সিভ)
#include <bits/stdc++.h>
using namespace std;
class node { public: int data; node* next; };
node* _kAltReverse(node* Node, int k, bool b);
node* kAltReverse(node* head, int k) { return _kAltReverse(head, k, true); }
node* _kAltReverse(node* Node, int k, bool b) {
if (!Node) return NULL;
int count = 1;
node *prev = NULL, *current = Node, *next;
while (current && count <= k) {
next = current->next;
if (b) current->next = prev;
prev = current;
current = next;
count++;
}
if (b) {
Node->next = _kAltReverse(current, k, !b);
return prev;
} else {
prev->next = _kAltReverse(current, k, !b);
return Node;
}
}
void push(node** head_ref, int new_data) {
node* new_node = new node();
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
void printList(node* node) {
while (node) { cout << node->data << " "; node = node->next; }
}
int main() {
node* head = NULL;
for (int i = 20; i > 0; i--) push(&head, i);
cout << "Given linked list \n"; printList(head);
head = kAltReverse(head, 3);
cout << "\nModified Linked list \n"; printList(head);
return 0;
}
আউটপুট
Given linked list: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Modified Linked list: 3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19
উপসংহার
আল্টারনেট K নোড রিভার্স করার ইটারেটিভ ও রিকার্সিভ দুটি পদ্ধতি দেখানো হয়েছে।
