Pythonで連結リストが回文になっているかどうかを判定するプログラム

連結リスト（リンクリスト）が与えられたとき、その要素が回文を形成しているかどうかを判定することを考えます。例えば、リストの要素が [5,4,3,4,5] のような並びであれば回文ですが、[5,4,3,2,1] のような並びは回文ではありません。

この問題を解くために、ここでは「2つのポインタ（fast・slow）」を使った効率的な手法を採用します。前半部分を走査しながら逆順に連結し直し、後半部分と比較することで、追加のメモリをほとんど使わずに判定できます。

アルゴリズムの手順

• fast := head、slow := head、rev := None、flag := 1 として初期化する
• head が空の場合は true を返す
• fast および fast の次のノードが存在する間、以下を繰り返す
  • fast の次の次のノードが存在しない場合、flag := 0 に設定してループを抜ける
  • fast := fast の次の次のノード
  • temp := slow、slow := slow の次のノード
  • temp の次 := rev とし、rev := temp とする（前半部分を逆順に構築）
• fast := slow の次のノードとし、slow の次 := rev とする
• flag が立っている場合（奇数長のリストの場合）、slow := slow の次のノードとして中央の要素をスキップする
• fast と slow がどちらも None でない間、以下を繰り返す
  • fast の値と slow の値が一致しない場合は false を返す
  • fast := fast の次のノード、slow := slow の次のノード
• true を返す

それでは、以下の実装例を見て理解を深めましょう。

実装例

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([5,4,3,4,5])
ob1 = Solution()
print(ob1.isPalindrome(head))

仕組みのポイント

このアルゴリズムでは、fast ポインタは2つずつ、slow ポインタは1つずつ進みます。fast が終端に到達した時点で、slow はリストの中央付近に位置しています。その間に slow が通過したノードは rev を使って逆順につなぎ変えられており、これにより前半部分が反転された状態になります。あとは反転した前半（rev 側）と後半（fast 側）を先頭から順に比較すればよく、奇数長のリストの場合は中央の要素をスキップするため flag を利用しています。計算量は時間 O(n)、追加メモリ O(1) で済むのが大きな利点です。

入力

[5,4,3,4,5]

出力

True