ইনপুট হিসাবে একটি একক লিঙ্ক তালিকা দেওয়া হয়েছে. মূল তালিকার বিকল্প নোড আছে এমন দুটি একক লিঙ্কযুক্ত তালিকায় তালিকাটিকে বিভক্ত করা লক্ষ্য। যদি ইনপুট তালিকায় নোড থাকে a → b → c → d → e → f তাহলে বিভক্ত হওয়ার পরে, দুটি উপ-তালিকা হবে একটি → c → e এবং b → d → f৷
আমরা N1 এবং N2 দুটি পয়েন্টার নেব যার একটি মূল তালিকার মাথার দিকে নির্দেশ করে এবং আরেকটি → পরের দিকে নির্দেশ করে। এখন উভয় পয়েন্টারকে পরবর্তী নোডের পরবর্তীতে নিয়ে যান এবং সাবলিস্ট তৈরি করুন।
উদাহরণ
ইনপুট − তালিকা :- 1 → 5 → 7 → 12 → 2 → 96 → 33
আউটপুট − মূল তালিকা :1 5 7 12 2 96 33
তালিকা 1:1 7 2 33
তালিকা 2:5 12 96
ব্যাখ্যা − 1 এবং 5 থেকে শুরু করুন এবং উপরে দেখানো সাবলিস্ট তৈরি করতে বিকল্প নোডের পরবর্তী পয়েন্টে যান৷
ইনপুট − তালিকা :- 13 → 53 → 90 → 18 → 44 → 11→ 99 → 32
আউটপুট − মূল তালিকা :13 53 90 18 44 11 99 32
তালিকা 1:13 90 44 99
তালিকা 2:53 18 11 32
ব্যাখ্যা − 13 এবং 53 থেকে শুরু করুন এবং উপরে দেখানো সাবলিস্ট তৈরি করতে বিকল্প নোডের পরের পয়েন্টে যান৷
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
এই পদ্ধতিতে আমরা N1 এবং N2 দুটি পয়েন্টার নেব যার একটি মূল তালিকার মাথার দিকে নির্দেশ করে এবং আরেকটি → পরের দিকে নির্দেশ করে। এখন উভয় পয়েন্টারকে পরবর্তী নোডের পরবর্তীতে নিয়ে যান এবং সাবলিস্ট তৈরি করুন।
-
int ডেটা অংশ সহ স্ট্রাকচার নোড এবং পরবর্তী পয়েন্টার হিসাবে নোড নিন।
-
ফাংশন addtohead(Node** head, int data) এককভাবে লিঙ্ক করা তালিকা তৈরি করতে মাথায় নোড যোগ করতে ব্যবহৃত হয়।
-
প্রথম নোডের পয়েন্টার হিসাবে উপরের ফাংশনটি ব্যবহার করে একটি একক লিঙ্কযুক্ত তালিকা তৈরি করুন।
-
হেড নোড থেকে শুরু করে লিঙ্ক করা তালিকা প্রিন্ট করতে ফাংশন ডিসপ্লে (নোড* হেড) ব্যবহার করা হয়।
-
দুটি নোড পয়েন্টার node1 এবং node2 নিন।
-
ফাংশন স্প্লিটলিস্ট(নোড* হেড, নোড** n1, নোড** n2) নোড পয়েন্টার এবং পয়েন্ট n1 কে হেড এবং n2 থেকে হেড → মূল স্ট্রিং এর পরের দিকে নিয়ে যায়।
-
এর ভিতরে মূল তালিকাকে দুটি সাবলিস্টে বিভক্ত করতে স্প্লিট (*n1, *n2) কল করুন
-
ফাংশন বিভক্ত (নোড* N1, নোড* N2) N1 এবং N2 পয়েন্টার নেয় এবং মূল তালিকার বিকল্প নোড সহ দুটি সাবলিস্ট তৈরি করে।
-
যদি N1 এবং N2 উভয়ই শূন্য হয় তবে কিছুই ফেরত দেবেন না।
-
N1→ পরবর্তী শূন্য না হলে tmp=N1->next->next এবং N1->next =tmp;
সেট করুন। -
f N2→ পরবর্তী শূন্য না হলে tmp=N2->পরবর্তী->পরবর্তী এবং N2->পরবর্তী =tmp;
সেট করুন -
কল স্প্লিট (N1->পরবর্তী, N2->পরবর্তী); পরবর্তী পুনরাবৃত্তির জন্য।
-
শেষে প্রদর্শন() ব্যবহার করে সাবলিস্ট প্রিন্ট করুন।
উদাহরণ
#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
