二重にリンクされた文字のリストがC++で回文であるかどうかを確認します

ここでは、文字列が回文であるか、二重リンクリストを使用していないかを確認する方法を説明します。ここでは、文字列の各文字を1つの二重リンクリスト内にプッシュします。左と右の2つのポインタがあります。次に、両側からスキャンを開始します。左の文字が右の文字と同じである場合は、左のポインタを次のノードに移動し、右のポインタを前のノードに移動します。それ以外の場合は、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