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