मान लीजिए कि हमारे पास एक लिंक की गई सूची है, हमें एक बार में लिंक की गई सूची k के नोड्स को उलटना होगा और इसकी संशोधित सूची को वापस करना होगा। यहाँ k एक धनात्मक पूर्णांक है और लिंक की गई सूची की लंबाई से कम या उसके बराबर है। इसलिए यदि नोड्स की संख्या k का गुणज नहीं है, तो अंत में बचे हुए नोड्स को यथावत रहना चाहिए।
इसलिए अगर लिंक की गई सूची [1,2,3,4,5,6,7] जैसी है और k 3 है, तो परिणाम [3,2,1,6,5,4,7] होगा।पी>
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
हल () नामक एक विधि को परिभाषित करें, यह लिंक की गई सूची का प्रमुख लेगा, पार्टकाउंट और k को लेगा
-
अगर पार्टकाउंट 0 है, तो हेड रिटर्न करें
-
न्यूहेड:=हेड, पिछला:=नल, एक्स:=के
-
जबकि न्यूहेड शून्य नहीं है और x 0 नहीं है
-
अस्थायी:=न्यूहेड के आगे, अगले हेड के आगे:=पिछला
-
पिछला:=नया सिर, नया सिर:=अस्थायी
-
-
सिर के आगे:=हल करें (नया हेड, पार्टकाउंट -1, के)
-
पिछली वापसी
-
मुख्य विधि से निम्न कार्य करें -
-
रिटर्न सॉल्व (लिंक की गई सूची का प्रमुख, सूची की लंबाई / k, k)
उदाहरण
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } void print_vector(vector<vector<auto>> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << "["; for(int j = 0; j <v[i].size(); j++){ cout << v[i][j] << ", "; } cout << "],"; } cout << "]"<<endl; } 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){ cout << ptr->val << ", "; ptr = ptr->next; } cout << "]" << endl; } class Solution { public: ListNode* solve(ListNode* head, int partitionCount, int k){ if(partitionCount == 0)return head; ListNode *newHead = head; ListNode* prev = NULL; ListNode* temp; int x = k; while(newHead && x--){ temp = newHead->next; newHead->next = prev; prev = newHead; newHead = temp; } head->next = solve(newHead, partitionCount - 1, k); return prev; } int calcLength(ListNode* head){ int len = 0; ListNode* curr = head; while(curr){ len++; curr = curr->next; } return len; } ListNode* reverseKGroup(ListNode* head, int k) { int length = calcLength(head); return solve(head, length / k, k); } }; main(){ vector<int> v = {1,2,3,4,5,6,7}; ListNode *head = make_list(v); Solution ob; print_list(ob.reverseKGroup(head, 3)); }
इनपुट
1,2,3,4,5,6,7 3
आउटपुट
[3, 2, 1, 6, 5, 4, 7, ]