Kiểm tra danh sách liên kết đôi ký tự có phải palindrome trong C++

Chúng ta sẽ kiểm tra một chuỗi có phải palindrome hay không bằng danh sách liên kết đôi (doubly linked list). Mỗi ký tự của chuỗi được đẩy vào danh sách. Sử dụng hai con trỏ left và right trỏ đến đầu và cuối danh sách. So sánh ký tự tại hai con trỏ, nếu giống nhau thì di chuyển left tiến tới, right lùi lại. Nếu khác nhau thì trả về false. Tiếp tục cho đến khi left và right trùng nhau hoặc right đứng ngay trước left.

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";
}

Kết quả

This is Palindrome