मान लीजिए हमारे पास एक लिंक्ड सूची है। हमें हर दो आसन्न नोड्स (जोड़ी) को स्वैप करना होगा और उसके सिर को वापस करना होगा। यहां बाधा यह है कि, हम नोड्स के मान को संशोधित नहीं कर सकते हैं, केवल नोड को ही बदला जा सकता है। तो अगर सूची [1,2,3,4] जैसी है, तो परिणामी सूची [2,1,4,3] होगी।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- यदि सिर मौजूद नहीं है, तो सिर वापस करें
- पहला:=सिर, दूसरा:=सिर के आगे, डमी एक नया नोड है जिसका मान -1 है
- डमी के आगे :=पहला, और पिछला :=डमी
- जबकि दूसरा शून्य नहीं है
- अस्थायी:=सेकंड के आगे
- पहले के आगे :=दूसरे के बाद
- दूसरे के अगले:=पहले
- पिछला के आगे :=सेकंड
- पिछला :=पहले
- यदि अस्थायी शून्य नहीं है, तो पहला:=अस्थायी और दूसरा:=अगला तापमान, अन्यथा विराम
- डमी के आगे वापसी
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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,9,10,11,12,13,14,15};
ListNode *head = make_list(v);
print_list(ob.swapPairs(head));
} इनपुट
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} आउटपुट
[2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13,]