C++で双方向連結リストの文字列が回文かどうかを判定する方法

本記事では、双方向連結リスト（Doubly Linked List）を用いて、文字列が回文（パリンドローム）であるかどうかを判定する方法を解説します。

まず、判定対象となる文字列の各文字を、双方向連結リストに順番に挿入します。その後、「left」と「right」という2つのポインタを用意し、リストの両端から同時に走査を行います。leftが指す文字とrightが指す文字が一致していれば、leftポインタを次のノードへ、rightポインタを前のノードへそれぞれ移動します。文字が一致しなかった場合は、その時点でfalseを返します。この処理は、leftとrightが同じノードを指すようになるか、あるいはrightがleftの直前のノードを指す状態になるまで繰り返されます。最後まで比較を続けられれば、その文字列は回文であると判断できます。

回文とは

回文とは、「madam」「level」「しんぶんし」のように、前から読んでも後ろから読んでも同じになる文字列のことです。双方向連結リストは、各ノードが前後両方のノードへのポインタを持つデータ構造であるため、先頭から末尾への走査だけでなく、末尾から先頭への逆方向の走査も簡単に行えます。この特性を活かすことで、両端から中央へ向かって文字を比較していく回文判定を効率的に実装できます。

アルゴリズムの流れ

1. 文字列の各文字を双方向連結リストに挿入します。
2. leftポインタを先頭ノードに、rightポインタを末尾ノードに設定します。
3. leftとrightが指す文字を比較し、一致しなければfalseを返します。
4. 一致していれば、leftを次のノードへ、rightを前のノードへ移動します。
5. leftとrightが出会う（または交差する）まで手順3〜4を繰り返し、最後まで一致すればtrueを返します。

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;
   // rightポインタを末尾ノードまで移動
   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

サンプルでは「madam」という回文の文字列を使用しているため、プログラムは「This is Palindrome（これは回文です）」と出力します。「hello」など回文ではない文字列に変更すれば、「This is Not a Palindrome」と表示されます。

計算量について

このアルゴリズムの時間計算量はO(n)です（nは文字列の長さ）。左右のポインタは合計でリスト全体を一度ずつ走査するのみなので、線形時間で判定が完了します。空間計算量については、リストを新規に構築する場合はO(n)が必要ですが、すでに存在するリストに対して判定を行う場合は、ポインタ2個分の追加メモリだけで済みます。