234. Palindrome Linked Listを解く

問題へのリンク

問題概要

単連結リストheadが与えられる．
このとき，与えられたリストが回文である場合はtrueそうでない場合はfalseを返す．

例：

Input: head = [1,2,2,1]
Output: true

制約

• リストに含まれるノードの数$[1,10^5]$
• $0 \leq Node.val \leq 9$

考えたこと

headを前から順にみていき，配列Lにノードの値を格納していく．
ノードの末尾に行き着いたらL == L[::-1]を評価すれば良いと考えた．

class Solution(object):
    def isPalindrome(self, head):
        L = []
        while head:
            L.append(head.val)
            head = head.next
        return L == L[::-1]

この実装では$O(n)$の空間計算量が必要なので，$O(n)$の計算時間かつ$O(1)$の空間計算量というフォローアップ問題の条件に対応していない．

従って，何らかの工夫を行い使用メモリを削減する必要がある．

ここでは，２つのポインターを用いて左半分と右半分のノードを比較することで回文かどうか検証する方法を実装する．

まず，ノードの長さが不明な中で左半分と右半分のノードに分けるには

• fast, slowの二つのポインターを用意する
• fastは１ステップで２ノード進む
• slowは１ステップで1ノード進む

というように設定すれば良い．

例えば，例に示した問題の場合は

初期状態：

f
1 -> 2 -> 2 -> 1 -> null
s

１ステップ：

          f
1 -> 2 -> 2 -> 1 -> null
     s

２ステップ：

                    f
1 -> 2 -> 2 -> 1 -> null
          s

のように，ノードの中間点にslowのポインターが位置していることが分かる．

左半分はheadを前から順に辿れば良いが，右半分はこのままでは逆順に辿ることになるため，以下のようにノードを反転して再構築する必要がある．

1 -> 2 -> 2 -> 1 -> null
          s

1 -> 2  null <- 2   1 -> null
                    s

1 -> 2  null <- 2 <- 1  null
                    　  s

ここまで出来たら左側のノードLと右側のノードRを先頭から順に比較して行けば良い．

以上の考えを実装したアルゴリズムを以下に示す：

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        R = None
        while slow:
            nxt = slow.next
            slow.next = R
            R = slow
            slow = nxt
        
        while R:
            if R.val != head.val:
                return False
            R = R.next
            head = head.next
        return True