C++ में लिस्ट विभाजन (Partition List)

मान लीजिए हमारे पास एक लिंक्ड लिस्ट और एक मान x है। हमें विभाजन करना है। विभाजन इस तरह कि x से कम सभी नोड्स उन नोड्स से पहले आएं जो x से बड़े या बराबर हैं। हमें इन दो विभाजनों में से प्रत्येक में नोड्स के मूल सापेक्ष क्रम को संरक्षित रखना चाहिए। यदि लिस्ट [1,4,3,2,5,2] है और x = 3, तो आउटपुट [1,2,2,4,3,5] होगा।

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

• डमी नोड्स d1 और d2 बनाएं, और उन्हें -1 से आरंभ करें, दो पॉइंटर्स dp1 और dp2 बनाएं, वे d1 और d2 को इंगित कर रहे हैं।
• जब तक a null नहीं है:
  • यदि a का मान < b:
    • dp1 का next := a के मान वाला नया नोड
    • dp1 := dp1 का next पॉइंटर
  • अन्यथा:
    • dp2 का next := a के मान वाला नया नोड
    • dp2 := dp2 का next पॉइंटर
  • a := a का next
• dp1 का next := d2 का next
• d1 का 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* partition(ListNode* a, int b) {
        ListNode* dummy1 = new ListNode(-1);
        ListNode* dummy2 = new ListNode(-1);
        ListNode* dummyPtr1 = dummy1;
        ListNode* dummyPtr2 = dummy2;
        while(a){
            if(a->val < b){
                dummyPtr1->next = new ListNode(a->val);
                dummyPtr1 = dummyPtr1->next;
            }
            else{
                dummyPtr2->next = new ListNode(a->val);
                dummyPtr2 = dummyPtr2->next;
            }
            a = a->next;
        }
        dummyPtr1->next = dummy2->next;
        return dummy1->next;
    }
};

int main(){
    Solution ob;
    vector<int> v = {1,4,6,3,2,5,2,8};
    ListNode *head = make_list(v);
    print_list(ob.partition(head, 3));
}

इनपुट

[1,4,6,3,2,5,2,8] 3

आउटपुट

[1, 2, 2, 4, 6, 3, 5, ]