C++-এ লিঙ্কড লিস্টকে পরিবর্তনশীল ভাবে ভাগ করার রিকারসিভ পদ্ধতি

একটি সিঙ্গলি লিঙ্কড লিস্ট দেওয়া থাকলে, সেটিকে দুটি সিঙ্গলি লিঙ্কড লিস্টে ভাগ করতে হবে যাতে মূল লিস্টের পরিবর্তনশীল নোডগুলো পৃথক হয়।

যেমন: লিস্ট = a → b → c → d → e → f হলে, ভাগ করার পর দুটি সাব-লিস্ট হবে: a → c → e এবং b → d → f।

উদাহরণ

ইনপুট − লিস্ট: 1 → 5 → 7 → 12 → 2 → 96 → 33

আউটপুট − মূল লিস্ট: 1 5 7 12 2 96 33

লিস্ট ১: 1 7 2 33

লিস্ট ২: 5 12 96

ব্যাখ্যা − ১ ও ৫ থেকে শুরু করে পরিবর্তনশীল নোডগুলো পয়েন্ট করিয়ে সাব-লিস্ট তৈরি করা হয়েছে।

ইনপুট − লিস্ট: 13 → 53 → 90 → 18 → 44 → 11 → 99 → 32

আউটপুট − মূল লিস্ট: 13 53 90 18 44 11 99 32

লিস্ট ১: 13 90 44 99

লিস্ট ২: 53 18 11 32

ব্যাখ্যা − ১৩ ও ৫৩ থেকে শুরু করে পরিবর্তনশীল নোডগুলো পয়েন্ট করিয়ে সাব-লিস্ট তৈরি করা হয়েছে।

প্রোগ্রামে ব্যবহৃত পদ্ধতি

দুটি পয়েন্টার N1 ও N2 নেওয়া হয়, একটি হেডে আরেকটি হেড->next-এ। তারপর উভয় পয়েন্টারকে next->next এ বাড়িয়ে সাব-লিস্ট তৈরি করা হয়।

Node স্ট্রাকচার: int data ও Node* next।
addtohead(Node** head, int data) ফাংশন দিয়ে লিস্ট তৈরি করুন।
display(Node* head) ফাংশন দিয়ে লিস্ট প্রিন্ট করুন।
দুটি নোড পয়েন্টার node1 ও node2 নিন।
splitList(Node* head, Node** n1, Node** n2) ফাংশনে n1 হেডে, n2 হেড->next-এ পয়েন্ট করান।
তারপর split(*n1, *n2) কল করে লিস্ট ভাগ করুন।
split(Node* N1, Node* N2) ফাংশনে:
• যদি N1 ও N2 NULL হয়, ফেরত যান।
• N1->next NULL নহলে tmp = N1->next->next; N1->next = tmp;
• N2->next NULL নহলে tmp = N2->next->next; N2->next = tmp;
• split(N1->next, N2->next) কল করুন।
শেষে display() দিয়ে সাব-লিস্ট প্রিন্ট করুন।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node* next;
};

void addtohead(Node** head, int data){
    Node* nodex = new Node;
    nodex->data = data;
    nodex->next = (*head);
    (*head) = nodex;
}

void split(Node* N1, Node* N2){
    Node *tmp;
    if (N1 == NULL || N2 == NULL){
        return;
    }
    if (N1->next != NULL){
        tmp = N1->next->next;
        N1->next = tmp;
    }
    if (N2->next != NULL){
        tmp = N2->next->next;
        N2->next = tmp;
    }
    split(N1->next, N2->next);
}

void splitList(Node* head, Node** n1, Node** n2){
    *n1 = head;
    *n2 = head->next;
    split(*n1, *n2);
}

void display(Node* head){
    Node* curr = head;
    if (curr != NULL){
        cout << curr->data << " ";
        display(curr->next);
    }
}

int main(){
    Node* head = NULL;
    Node *node1 = NULL, *node2 = NULL;
    addtohead(&head, 20);
    addtohead(&head, 12);
    addtohead(&head, 15);
    addtohead(&head, 8);
    addtohead(&head, 10);
    addtohead(&head, 4);
    addtohead(&head, 5);
    cout << "Original List :" << endl;
    display(head);
    splitList(head, &node1, &node2);
    cout << endl << "List 1: ";
    display(node1);
    cout << endl << "List 2: ";
    display(node2);
    return 0;
}

আউটপুট

উপরের কোড রান করলে নিচের আউটপুট পাওয়া যাবে:

Original List : 5 4 10 8 15 12 20 List 1: 5 10 15 20 List 2: 4 8 12