Pythonで単方向リンクリスト（片方向連結リスト）が回文かどうかを判定する方法

単方向リンクリスト（片方向連結リスト）が回文になっているかどうかを確認したい場合は、「要素を追加するメソッド」「指定したノードの前のノードを取得するメソッド」「回文かどうかを判定するメソッド」を定義することで実現できます。
以下に具体的な実装例を示します。

サンプルコード

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList_struct:
    def __init__(self):
        self.head = None
        self.last_node = None

    def add_elements(self, data):
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next

    def get_previous_node(self, ref_node):
        curr = self.head
        while (curr and curr.next != ref_node):
            curr = curr.next
        return curr


def check_palindrome(my_list):
    beg = my_list.head
    end = my_list.last_node
    while (beg != end and end.next != beg):
        if beg.data != end.data:
            return False
        beg = beg.next
        end = my_list.get_previous_node(end)
    return True


my_instance = LinkedList_struct()

my_input = input('リンクリストに追加する要素を入力してください: ').split()
for data in my_input:
    my_instance.add_elements(int(data))

if check_palindrome(my_instance):
    print('このリンクリストは回文です')
else:
    print('このリンクリストは回文ではありません')

実行結果

リンクリストに追加する要素を入力してください: 89 90 78 90 89
このリンクリストは回文です

コードの解説

• まず、データ（data）と次ノードへの参照（next）を持つ「Node」クラスを作成します。

• 必要な属性を持つ「LinkedList_struct」クラスを定義します。

• __init__関数では、先頭ノード（head）と末尾ノード（last_node）をNoneで初期化します。

• add_elementsメソッドは、リストが空の場合はheadに新しいノードを設定し、それ以外の場合はlast_nodeのnextに新しいノードを追加してlast_nodeを更新します。

• get_previous_nodeメソッドは、リストを先頭から辿り、指定された参照ノードの直前のノードを取得します。

• check_palindromeメソッドは、先頭ノード（beg）と末尾ノード（end）のデータを比較します。一致しなければそのリストは回文ではないと判断してFalseを返します。一致した場合はbegを次のノードへ進め、endを前のノードへ戻しながら比較を繰り返します。begとendが出会えば全ての対称位置が一致していることになり、Trueを返します。

• 「LinkedList_struct」クラスのインスタンスを作成します。

• ユーザーからリンクリストに格納する要素を入力として受け取ります。

• 入力された各要素をリンクリストへ追加します。

• check_palindromeメソッドを呼び出して、リンクリストが回文かどうかを判定します。

• 判定結果に応じたメッセージがコンソールに表示されます。

計算量に関する補足

get_previous_nodeは呼び出されるたびにリストを先頭から走査するため、この実装の時間計算量はO(n²)となります。より効率的にしたい場合は、ノードの値を通常のリスト（配列）にコピーして前後から比較する方法や、リストの中間地点まで進んだうえで後半部分を反転させ、前半と照合するO(n)のアルゴリズムが知られています。用途やデータサイズに応じて使い分けるとよいでしょう。