이중 연결 문자 목록이 C++에서 회문인지 확인하십시오.

여기에서 문자열이 회문인지 이중 연결 목록을 사용하지 않는지 확인하는 방법을 살펴보겠습니다. 여기서는 문자열의 각 문자를 하나의 이중 연결 목록 안에 밀어넣을 것입니다. 왼쪽과 오른쪽의 두 포인터가 있습니다. 그런 다음 양면에서 스캔을 시작합니다. 왼쪽 문자가 오른쪽 문자와 같으면 왼쪽 포인터를 다음 노드로 이동하고 오른쪽 포인터를 이전 노드로 이동합니다. 그렇지 않으면 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