ที่นี่เราจะดูวิธีการตรวจสอบสตริงเป็น palindrome หรือไม่ใช้รายการเชื่อมโยงแบบทวีคูณ ที่นี่เราจะผลักอักขระแต่ละตัวของสตริงในรายการที่เชื่อมโยงเป็นสองเท่า จะมีพอยน์เตอร์สองตัว ซ้ายและขวา จากนั้นเริ่มสแกนจากทั้งสองด้าน หากอักขระด้านซ้ายเหมือนกับอักขระด้านขวา ให้ย้ายตัวชี้ด้านซ้ายไปยังโหนดถัดไป และย้ายตัวชี้ไปทางขวาไปยังโหนดก่อนหน้า มิฉะนั้นให้คืนค่าเท็จ กระบวนการนี้จะดำเนินต่อไปจนกว่าซ้ายและขวาจะชี้ไปที่โหนดเดียวกัน หรือตัวชี้ขวาจะชี้ไปที่องค์ประกอบก่อนหน้าของตัวชี้ด้านซ้าย
ตัวอย่าง
#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
