C++ में k-ग्रुप में नोड्स को उल्टा करना

मान लीजिए हमारे पास एक लिंक्ड लिस्ट है, हमें लिंक्ड लिस्ट के नोड्स को k के समूह में उल्टा करना है और इसकी संशोधित लिस्ट वापस करनी है। यहां k एक सकारात्मक पूर्णांक है और लिंक्ड लिस्ट की लंबाई से कम या बराबर है। यदि नोड्स की संख्या k का गुणक नहीं है तो अंत में बचे हुए नोड्स वैसे ही रहने चाहिए।

यदि लिंक्ड लिस्ट [1,2,3,4,5,6,7] है और k 3 है, तो परिणाम [3,2,1,6,5,4,7] होगा।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• solve() नामक एक विधि परिभाषित करें, जो लिंक्ड लिस्ट का हेड, partCount और k लेती है
• यदि partCount 0 है, तो हेड वापस करें
• newHead := हेड, prev := null, x := k
• जब तक newHead null नहीं है और x 0 नहीं है:
  • temp := newHead का अगला, newHead का अगला := prev
  • prev := newHead, newHead := temp
• हेड का अगला := solve(newHead, partCount - 1, k)
• prev वापस करें
• मुख्य विधि से निम्नलिखित करें:
  • solve(लिंक्ड लिस्ट का हेड, लिस्ट की लंबाई / k, k) वापस करें

उदाहरण (C++ कोड)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#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); 
    } 
}; 
int 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, ]