বিবেচনা করুন আমাদের একটি লিঙ্ক করা তালিকা আছে৷ আমাদের প্রতি দুটি সংলগ্ন নোড অদলবদল করতে হবে এবং এর মাথাটি ফিরিয়ে দিতে হবে। সীমাবদ্ধতা হল আমরা নোডের মান পরিবর্তন করতে পারি না, শুধুমাত্র নোড নিজেই পরিবর্তন করা যেতে পারে। তাই যদি তালিকাটি [1,2,3,4] এর মত হয়, তাহলে ফলাফলের তালিকাটি হবে [2,1,4,3]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- হেড না থাকলে, হেড রিটার্ন করুন
- প্রথম :=মাথা, দ্বিতীয় :=মাথার পরের, ডামি হল একটি নতুন নোড যার মান -1
- ডামির পাশে :=প্রথম, এবং পূর্বে :=ডামি
- যদিও দ্বিতীয়টি শূন্য নয়
- temp :=সেকেন্ডের পরের
- প্রথমটির পরের :=দ্বিতীয়টির পরের
- সেকেন্ডের পরের :=প্রথম
- পূর্বের পরের :=সেকেন্ড
- আগের :=প্রথম
- যদি temp নাল না হয়, তাহলে প্রথমে :=temp এবং দ্বিতীয় :=temp এর পরের, অন্যথায় বিরতি
- ডামির পরের রিটার্ন
উদাহরণ(C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
void print_list(ListNode *head){
ListNode *ptr = head;
cout << "[";
while(ptr->next){
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << "]" << endl;
}
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(!head)return head;
ListNode* first= head;
ListNode* second = head->next;
ListNode* dummy = new ListNode(-1);
dummy->next = first;
ListNode* prev = dummy;
while(second){
ListNode* temp = second->next;
first->next = second->next;
second->next = first;
prev->next = second;
prev = first;
if(temp){
first = temp;
second = temp ->next;
}
else break;
}
return dummy->next;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,5,6,7,8};
ListNode *head = make_list(v);
print_list(ob.swapPairs(head));
} ইনপুট
[1,2,3,4,5,6,7,8]
আউটপুট
[2,1,4,3,6,5,8,7]
