📌 문제

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

주어진 linkedlist가 회문인지 판단하라.

📌 아이디어

deque에 담아놓고, popleft() 와 pop() 을 비교해서 일치하지 않으면 False, loop를 빠져나오면 True를 return

list로 선언해서 pop(0)와 pop()을 비교할 수도 있는데, list의 경우 pop(0)연산을 한 뒤 나머지 요소들을 재정렬하는데 O(n)이 걸리므로 deque를 이용해야 한다.
( 정렬후 요소들이 왼쪽으로 shifting된다 )

📌 코드

# https://leetcode.com/problems/palindrome-linked-list/
from collections import deque


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        q = deque()
        node = head
        while node:
            q.append(node.val)
            node=node.next
        while len(q)>1:
            if q.popleft() != q.pop():
                return False
        return True