Palindrome Linked List

# 問題

次のように定義される連結リストが与えられる．

1
2
3
4
5
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

与えられた連結リストが回分になっているか判定せよ．

# 解法

回分になっているかを知るためにはとりあえず真ん中がほしいので，🐰と🐢が使える

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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: Optional[ListNode]) -> bool:
        if head is None:
            return None
        faster = head
        slower = head
        while faster is not None and faster.next is not None:
            faster = faster.next.next
            slower = slower.next
        stack = []
        while slower is not None:
            stack.append(slower.val)
            slower = slower.next
        current = head
        while len(stack) != 0:
            if stack.pop() != current.val:
                return False
            current = current.next
        return True

# 出典

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