সমস্যা বিবরণ
একটি লিংকড লিস্ট দেওয়া আছে। প্রতিটি দুটি আডজেসেন্ট নোড স্ব্যাপ করতে হবে এবং হেড রিটার্ন করতে হবে। নোডের মান পরিবর্তন করা যাবে না, শুধু নোডের লিংক পরিবর্তন করা যাবে।
উদাহরণ: লিস্ট [1,2,3,4] হলে ফলাফল [2,1,4,3] হবে।
সমাধানের ধাপসমূহ
- যদি হেড না থাকে, তবে হেড রিটার্ন করুন।
- first := head, second := head->next, dummy := নতুন নোড মান -1।
- dummy->next := first, prev := dummy।
- যখন second নাল নয়:
- temp := second->next
- first->next := second->next
- second->next := first
- prev->next := second
- prev := first
- যদি temp নাল না হয়, তবে first := temp এবং second := temp->next, অন্যথায় ব্রেক।
- dummy->next রিটার্ন করুন।
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;
}
};
int 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]
