একটি লিঙ্ক করা তালিকা হল একটি রৈখিক ডেটা কাঠামো যেখানে প্রতিটি নোডে দুটি ব্লক থাকে যেমন একটি ব্লকে নোডের মান বা ডেটা থাকে এবং অন্য ব্লকে পরবর্তী ক্ষেত্রের ঠিকানা থাকে৷
আসুন আমরা ধরে নিই যে আমাদের একটি লিঙ্কযুক্ত তালিকা রয়েছে যাতে প্রতিটি নোডে ডেটা এবং একটি পয়েন্টার থাকে যা লিঙ্কযুক্ত তালিকার পরবর্তী নোডের দিকে নির্দেশ করে। টাস্ক হল প্রদত্ত লিঙ্কযুক্ত তালিকাকে আলাদা করা। লিঙ্ক করা তালিকা আলাদা করার অর্থ হল আমাদের তালিকার বিজোড় সূচীযুক্ত নোড এবং এমনকি সূচক নোডগুলিকে আলাদা করতে হবে৷
এই সমস্যা সমাধানের পদ্ধতি
একটি প্রদত্ত লিঙ্কযুক্ত তালিকাকে আলাদা করতে, আমরা যথাক্রমে জোড় সূচক, জোড় সূচক এবং জোড় সূচকে মানটির জন্য তিনটি পয়েন্টার প্রবর্তন করব। এর পরে, আমরা পুরো লিঙ্কযুক্ত তালিকার উপর পুনরাবৃত্তি করব এবং কিছু মান সহ পয়েন্টার শুরু করব।
লিঙ্ক করা তালিকায়, সূচীকরণ '1' থেকে শুরু হয়, এইভাবে কোনো নির্দিষ্ট স্ট্রিংয়ের জন্য, তালিকার প্রথম নোডটি সর্বদা একটি বিজোড় সূচীযুক্ত নোড হিসাবে বিবেচিত হবে। যাইহোক, পরবর্তী নোডটিকে একটি সমান সূচীযুক্ত নোড হিসাবে বিবেচনা করা হয়।
- ডাটা সহ একটি লিঙ্ক করা তালিকা নিন এবং পরবর্তী নোডে পয়েন্টার করুন।
- একটি ফাংশন সেগ্রিগেটলিস্ট(লিস্টনোড *হেড) পয়েন্টারটিকে হেড নোডে নিয়ে যায় এবং আউটপুট হিসাবে আলাদা করা লিঙ্কযুক্ত তালিকা ফিরিয়ে দেয়।
- তিনটি পয়েন্টার oddIndex, evenIndex এবং evenHead শুরু করুন যা বর্তমানে তালিকার প্রধানের দিকে নির্দেশ করছে।
- পুরো লিঙ্ক করা তালিকার উপর পুনরাবৃত্তি করুন এবং oddIndex এর পরবর্তী পয়েন্টারটি evenIndex এর পরবর্তী পয়েন্টার দিয়ে শুরু করুন।
- এখন পুরো তালিকার উপর পুনরাবৃত্তি করুন এবং oddIndex-এর পরবর্তী পয়েন্টার দিয়ে evenIndex-এর পরবর্তী পয়েন্টার শুরু করুন।
- হেড পয়েন্টার ফেরত দিন।
উদাহরণ
#include <iostream>
using namespace std;
class node {
public:
int data;
node * next;
node(int d) {
data = d;
next = NULL;
}
};
node * segregateList(node * head) {
if (head == NULL) {
return NULL;
}
node * oddIndex = head;
node * evenIndex = head -> next;
node * evenHead = evenIndex;
while (evenIndex != NULL and evenIndex -> next != NULL) {
oddIndex -> next = evenIndex -> next;
oddIndex = oddIndex -> next;
evenIndex -> next = oddIndex -> next;
evenIndex = evenIndex -> next;
}
oddIndex -> next = evenHead;
return head;
}
void insertAtNode(node * & head, int data) {
node * n = new node(data);
n -> next = head;
head = n;
}
void print(node * head) {
while (head != NULL) {
cout << head -> data << "->";
head = head -> next;
}
}
int main() {
node * head = NULL;
// It could be possible that the head node contains NULL Value.
insertAtNode(head, 5);
insertAtNode(head, 8);
insertAtNode(head, 3);
insertAtNode(head, 1);
insertAtNode(head, 2);
print(head);
cout << endl;
segregateList(head);
print(head);
} উপরের কোডটি চালানোর ফলে আউটপুট তৈরি হবে,
আউটপুট
2->3->5->1->8->
প্রদত্ত লিঙ্ক তালিকা হল, 2->1->3->8->5->। লিঙ্ক করা তালিকা আলাদা করার পরে, এটি 2->3->5->1->8-> হিসাবে আউটপুট তৈরি করবে।
