এখানে আমরা দেখব কিভাবে একটি ডাবলি লিংকড লিস্ট ব্যবহার করে একটি স্ট্রিং প্যালিনড্রোম কিনা তা যাচাই করা যায়। এখানে স্ট্রিংয়ের প্রতিটি ক্যারেক্টারকে একটি ডাবলি লিংকড লিস্টে পুশ করা হবে। দুটি পয়েন্টার থাকবে: বাম (left) এবং ডান (right)। তারপর উভয় পাশ থেকে স্ক্যানিং শুরু করা হবে। যদি বাম পাশের ক্যারেক্টার ডান পাশের ক্যারেক্টারের সাথে মিলে, তবে বাম পয়েন্টারকে পরবর্তী নোডে এবং ডান পয়েন্টারকে পূর্ববর্তী নোডে সরিয়ে নিতে হবে। অন্যথায় false রিটার্ন করবে। এই প্রক্রিয়া तबতক চলবে যতক্ষণ না বাম ও ডান পয়েন্টার একই নোডে নির্দেশ করে, অথবা ডান পয়েন্টার বাম পয়েন্টারের পূর্ববর্তী উপাদান নির্দেশ করে।
উদাহরণ
#include <iostream> using namespace std; class Node { public: char data; Node *next; Node *prev; }; void getNode(Node** start, char new_data) { struct Node* newNode = new Node; newNode->data = new_data; newNode->next = (*start); newNode->prev = NULL; if ((*start) != NULL) (*start)->prev = newNode ; (*start) = newNode; } bool isPalindrome(Node *left) { if (left == NULL) return true; Node *right = left; while (right->next != NULL) right = right->next; while (left != right && right != left->prev) { if (left->data != right->data) return false; left = left->next; right = right->prev; } return true; } int main() { Node* head = NULL; string str = "madam"; for(int i = 0; i< str.length(); i++){ getNode(&head, str[i]); } if (isPalindrome(head)) cout << "This is Palindrome"; else cout << "This is Not a Palindrome"; }আউটপুট
This is Palindrome
