LeetCode / Palindrome Linked List

最近、ニュースを見る度に過剰反応が報道されていていらついていたのでテレビを全く見なくなり、Youtube視聴に退避していたのですが、

ついに好きな旅行系Youtuberの方が投稿を休止される事態となり、残念、うんざりな思いが蓄積されていっている今日この頃です。

現実逃避に、LeetCodeの解説をします。

https://leetcode.com/problems/palindrome-linked-list/

Given a singly linked list, determine if it is a palindrome.

Example 1:
Input: 1->2
Output: false

Example 2:
Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

左右対称のlinked listかどうか判定する問題。Follow upに書かれている空間計算量の制約をクリアするのが骨です。

解法1

空間計算量のことを忘れれば、逆順のリストを用意し、一致を見ればよいだけなので簡単です。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        vals = []
        while head:
            vals += head.val,
            head = head.next
        return vals == vals[::-1]

これでは手応えがないので、空間計算量をに減らす方法を考えます。

解法2

空間計算量をとする方法となると、必然的に1つ1つのnodeを走査する方法しかない、となります。

結論から言えば、以下の手順をとります。

1. 真ん中のnodeを求める
2. 真ん中のnode以降のlinked listを逆順にしたlinked listを得る
3. 元のlinked listと2で得た逆順のlinked listが一致しているか確認する

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        fast = slow = head
        # 1. 真ん中のnodeを求める
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        # 2. 真ん中のnode以降のlinked listを逆順にしたlinked listを得る
        rev_half_head = None
        while slow:
            tmp = slow.next
            slow.next = rev_half_head
            rev_half_head = slow
            slow = tmp
        # 3. 元のlinked listと2で得た逆順のlinked listが一致しているか確認する
        while rev_half_head:
            if rev_half_head.val != head.val:
                return False
            rev_half_head = rev_half_head.next
            head = head.next
        return True

特に手順2のlinked listを空間計算量で逆順にするところがややこしいのですが、これはもう覚えてしまった方が良いかなと個人的には思っています。