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

연결 리스트가 팰린드롬 구조인지 판별

240110

리스트를 만들어 q.pop(0) != q.pop() 를 이용해 팰린드롬 구조를 판별하였으나
시간이 1220ms로 느린편이다.
이는 리스트의 경우 pop(0) 진행 시 모든 값이 한칸씩 시프팅 되기 때문에 시간 복잡도가 O(n)으로 발생하기 때문이다.

1. 양방향 모두 O(1)이 가능한 데크를 사용하자
   collection.deque()

2. != None 보다 is not None이 더 빠르다

3. input이 []일 때도 고려하자

4. 위 1~3 해결 후, 런너 기법 & 다중 할당 & 연결 리스트를 활용하여 문제해결하자 (p.210)

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


class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        
        number_list = []

        while head.next != None:
            number_list.append(head.val)
            head = head.next

        number_list.append(head.val)
        
        while len(number_list) > 1:
            if number_list.pop(0) != number_list.pop(-1):
                return False
            
        return True