ตรวจสอบว่า Doubly Linked List ของ Characters เป็น Palindrome หรือไม่ใน C++

ในบทความนี้เราจะมาดูวิธีการตรวจสอบว่า String เป็น Palindrome หรือไม่โดยใช้ Doubly Linked List เราจะนำแต่ละ Character ของ String ไปใส่ใน Doubly Linked List จะมี Pointer 2 ตัวคือ Left และ Right เริ่มตรวจสอบจากทั้งสองข้าง หาก Character ด้านซ้ายเท่ากับด้านขวา ให้เลื่อน Left ไป Next Node และ Right ไป Previous Node มิฉะนั้นคืนค่า false กระบวนการนี้ทำต่อจน Left และ Right ชี้ไปที่ Node เดียวกัน หรือ Right ชี้ไปที่ Node ก่อนหน้าของ Left

ตัวอย่างโค้ด C++

#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