C++ . में विभाजन सूची

मान लीजिए कि हमारे पास एक लिंक की गई सूची और एक मान 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 रिक्त नहीं है
  • अगर a का मान
  • dp1 के आगे :=एक मान के साथ एक नया नोड
  • dp1 :=dp1 का अगला पॉइंटर
• अन्यथा
  • dp2 के आगे :=एक मान के साथ एक नया नोड
  • dp2 :=dp2 का अगला पॉइंटर
• a :=a के आगे

उदाहरण(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;
   }
};
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, ]