첫 번째 제출

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from collections import deque
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        queue = deque()
        node = head
        while node is not None:
            queue.append(node.val)
            node = node.next
        
        while len(queue) > 1:
            if queue.popleft() != queue.pop():
                return False
        
        return True
        

+)

런너를 이용하면 자료형을 변환하지 않아서 더 우아하게 풀 수 있다고 한다.
하지만 런너는 다음에 더 자세히 알아볼 것이다.

• queue에서 첫 번째 인덱스 뽑기 : O(1) <- queue.popleft()
  list에서 첫 번째 인덱스 뽑기 : O(n) <- lst.pop(0)
  ㄴ list는 0번째 값을 뽑으면 뒤에 값들이 다시 한 칸씩 이동해야 하기 때문