Ở đây chúng ta sẽ thấy cách kiểm tra một chuỗi có phải là palindrome hay không bằng cách sử dụng danh sách liên kết Đôi. Ở đây, chúng tôi sẽ đẩy từng ký tự của một chuỗi vào trong một danh sách được liên kết kép. Sẽ có hai con trỏ, trái và phải. Sau đó, bắt đầu quét từ cả hai phía. Nếu một ký tự bên trái giống với ký tự bên phải, thì hãy di chuyển con trỏ bên trái đến nút tiếp theo và di chuyển con trỏ bên phải đến nút trước đó. Nếu không, trả về false. Quá trình này sẽ được tiếp tục cho đến khi bên trái và bên phải trỏ đến cùng một nút hoặc con trỏ bên phải trỏ đến phần tử trước đó của con trỏ bên trái.
Ví dụ
#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";
} Đầu ra
This is Palindrome