【Python】リンクリストが回文かどうかを判定するアルゴリズム

回文リンクリストとは

リンクリスト（連結リスト）が与えられたとき、その要素が回文（前から読んでも後ろから読んでも同じ並び）になっているかどうかを判定する問題です。例えば、リストの要素が [1,2,3,2,1] のような場合は回文であるため True を返し、[1,2,3] のような場合は回文ではないため False を返します。

アルゴリズムの手順

この問題は、fast / slow の2つのポインタを使ってリストの中央を特定し、前半部分を逆順に反転させたうえで後半部分と比較することで、追加メモリなしに O(n) 時間で解くことができます。

1. fast := head、slow := head、rev := None、flag := 1 で初期化します。
2. head が空（None）の場合は true を返します。
3. fast および fast の次のノードが存在する間、以下を繰り返します。
   • fast の2つ先のノードが存在しない場合は、flag := 0 に設定してループを抜けます（リスト長が偶数の場合）。
   • fast := fast の次の次のノード（2ノード先へ進めます）。
   • temp := slow、slow := slow の次のノード。
   • temp の次を rev につなぎ替え、rev := temp とします（前半部分を走査しながら逆順に構築していきます）。
4. fast := slow の次のノードとし、slow の次を rev につなぎ替えます。
5. flag が立っている場合（リスト長が奇数の場合）、slow := slow の次のノードとして中央のノードをスキップします。
6. fast と slow がどちらも None でない間、以下を繰り返します。
   • fast の値と slow の値が一致しない場合は false を返します。
   • fast := fast の次、slow := slow の次。
7. すべて一致すれば true を返します。

Pythonでの実装例

以下の実装を見ると、より理解が深まります。

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

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

class Solution(object):
    def isPalindrome(self, head):
        fast, slow = head, head
        rev = None
        flag = 1
        if not head:
            return True
        while fast and fast.next:
            if not fast.next.next:
                flag = 0
                break
            fast = fast.next.next
            temp = slow
            slow = slow.next
            temp.next = rev
            rev = temp
        fast = slow.next
        slow.next = rev
        if flag:
            slow = slow.next
        while fast and slow:
            if fast.data != slow.data:
                return False
            fast = fast.next
            slow = slow.next
        return True

head = make_list([1,2,3,2,1])
ob1 = Solution()
print(ob1.isPalindrome(head))

入力

[1,2,3,2,1]

出力

True

計算量について

このアルゴリズムはリスト全体を定数回走査するだけなので、時間計算量は O(n) です。また、リストを配列などにコピーせず、ポインタの付け替えだけで処理を行うため、空間計算量は O(1) となります。リストを一旦配列に変換して比較する方法（O(n) の追加メモリが必要）と比べてメモリ効率に優れている点が大きな特徴です。