C++-এ লিংকড লিস্ট পার্টিশন (Partition List)

একটি লিংকড লিস্ট এবং একটি ভ্যালু x দেওয়া আছে। লিস্টকে পার্টিশন করতে হবে যেন x-র চেয়ে ছোট ভ্যালুवाले নোডগুলো x-র চেয়ে বড় বা সমান ভ্যালুवाले নোডগুলোর আগে আসে। উভয় পার্টিশনে আসল রিলেটিভ অর্ডার রক্ষা করতে হবে।

উদাহরণ: [1,4,3,2,5,2], x=3 -> আউটপুট: [1,2,2,4,3,5]

সমাধান: দুটি ডামি নোড (d1, d2) এবং দুটি পয়েন্টার (dp1, dp2)। লিস্ট ট্রাভার্স করলে ছোট ভ্যালু dp1-এ, বড় ভ্যালু dp2-এ যোগ করব। শেষে 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; inext != 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, ]