Zenn
💭

234. Palindrome Linked List

に公開
PHP
TypeScript
leetcoce
tech

単方向リンクリストの先頭ノードが与えられたとき、それが回文であれば true を、そうでなければ false を返してください。

例1:

入力: head = [1,2,2,1]
出力: true

例2:

入力: head = [1,2]
出力: false

制約:

  • リスト内のノード数は [1, 10^5] の範囲です。
  • 0 <= Node.val <= 9

発展問題（Follow-up）:

O(n) 時間かつ O(1) 空間で解くことはできますか？

  • $slow と $fast を使ってリストの中央まで移動する
  • 中央に着いたら、$slow 以降のリストを逆順にする（後半部分の反転）
  • $head（先頭）からと、反転した $slow から一つずつ値を比較
    すべて一致すれば回文 → true
    一つでも違えば回文ではない → false

Discussion