# LeetCode Easy 234. Palindrome Linked List

tags: leetcode

問題

• Explore
• Problems

アイデア

｢単方向連結リストが与えられた時，それが左右対称か判定しろ｣という問題です．

実装するだけの問題ですね…これも(自力で出来なかった顔)

解法

• 連結リストリストを前半と後半に分けます．
  • ポインタを1つずつ動くものと，2つずつ動くものに分け，これによって中心のノードを特定します．
  • 中心のノードから後半部分のノードを反転させます．
• そして，反転させたノードとheadを比較して異なった値が出てくればFalseです
  • 出てこなければTrue

計算量

配列のノードの数を$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
            if not head:
                return True

            fast = slow = head
            while fast and fast.next:
                fast, slow = fast.next.next, slow.next

            rev = None
            while slow:
                next_node = slow.next
                slow.next = rev
                rev = slow
                slow = next_node

            while rev:
                if rev.val != head.val:
                    return False
                rev = rev.next
                head = head.next
            return True