এখানে আমরা দেখব কিভাবে একটি স্ট্রিং একটি প্যালিনড্রোম কিনা বা দ্বিগুণ লিঙ্কযুক্ত তালিকা ব্যবহার করে না। এখানে আমরা একটি স্ট্রিংয়ের প্রতিটি অক্ষরকে একটি দ্বিগুণ লিঙ্কযুক্ত তালিকার ভিতরে পুশ করব। দুটি পয়েন্টার থাকবে, বাম এবং ডান। তারপর উভয় দিক থেকে স্ক্যান করা শুরু করুন। যদি একটি বাম অক্ষর ডান অক্ষরের সমান হয়, তাহলে বাম পয়েন্টারটিকে পরবর্তী নোডে নিয়ে যান এবং ডান পয়েন্টারটিকে আগের নোডে নিয়ে যান। অন্যথায়, মিথ্যা ফিরে. এই প্রক্রিয়াটি চলতে থাকবে যতক্ষণ না বাম এবং ডান একই নোডে নির্দেশ করছে, বা ডান পয়েন্টারটি বাম পয়েন্টারের পূর্ববর্তী উপাদানের দিকে নির্দেশ করছে।
উদাহরণ
#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
