检查双向链接的字符列表是否在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