একটি সমস্যা সমাধান করতে হবে যেখানে একটি লিঙ্কড লিস্টের পেয়ারওয়াইজ নোডগুলো সওয়াপ (swap) করে প্রিন্ট করতে হবে। উদাহরণ −
ইনপুট: 1→2→3→4→5→6→NULL আউটপুট: 2→1→4→3→6→5→NULL ইনপুট: 1→2→3→4→5→NULL আউটপুট: 2→1→4→3→5→NULL ইনপুট: 1→NULL আউটপুট: 1→NULL
এই সমাধানের দুটি পদ্ধতি রয়েছে, উভয়ের টাইম কমপ্লেক্সিটি O(N), যেখানে N হলো লিঙ্কড লিস্টের সাইজ। এখন উভয় পদ্ধতি অন্বেষণ করব।
এই পদ্ধতিতে, আমরা লিঙ্কড লিস্টের এলিমেন্টগুলো ইটারেট (iterate) করব এবং পেয়ারওয়াইজ সওয়াপ করব NULL পাওয়া পর্যন্ত।
#include <bits/stdc++.h> using namespace std; class Node { // লিস্টের নোড public: int data; Node* next; }; void swapPairwise(Node* head){ Node* temp = head; while (temp != NULL && temp->next != NULL) { // পেয়ারওয়াইজ সওয়াপের জন্য ২টি নোড লাগে swap(temp->data, temp->next->data); // ডেটা সওয়াপ temp = temp->next->next; // পরবর্তী জোড়ায় যাওয়া } } 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 != NULL) { cout << node->data << " "; node = node->next; } } int main(){ Node* head = NULL; push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); cout << "Linked list before\n"; printList(head); swapPairwise(head); cout << "\nLinked list after\n"; printList(head); return 0; }
Linked list before 1 2 3 4 5 Linked list after 2 1 4 3 5
পরবর্তী পদ্ধতিতে আমরা একই লজিক রিকার্সন (recursion) দিয়ে ইমপ্লিমেন্ট করব।
এই পদ্ধতিতে, একই লজিক রিকার্সিভলি ইমপ্লিমেন্ট করা হয়েছে।
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; void swapPairwise(struct Node* head){ if (head != NULL && head->next != NULL) { // ইটারেটিভের মতো কন্ডিশন swap(head->data, head->next->data); // ডেটা সওয়াপ swapPairwise(head->next->next); // পরবর্তী জোড়ায় রিকার্সিভ কল } return; } 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 != NULL) { cout << node->data << " "; node = node->next; } } int main(){ Node* head = NULL; push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); cout << "Linked list before\n"; printList(head); swapPairwise(head); cout << "\nLinked list after\n"; printList(head); return 0; }
Linked list before 1 2 3 4 5 Linked list after 2 1 4 3 5
এই পদ্ধতিতে, আমরা লিঙ্কড লিস্টটি জোড়া জোড়া ট্রাভার্স করি। যেই জোড়ায় পৌঁছাই, তাদের ডেটা সওয়াপ করে পরবর্তী জোড়ায় যাই। ইটারেটিভ এবং রিকার্সিভ দুটি পদ্ধতিতেই একই লজিক কাজ করে।
এই টিউটোরিয়ালে আমরা লিঙ্কড লিস্টের পেয়ারওয়াইজ নোড সওয়াপ করার সমস্যা সমাধান করেছি রিকার্সন এবং ইটারেশন দুভাবেই। আমরা এই সমস্যার C++ প্রোগ্রাম ও সম্পূর্ণ পদ্ধতি দেখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়। আশা করি আপনি এই টিউটোরিয়ালটি সহায়ক পাবেন।
