✓[LeetCode] 234. Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

 

Constraints:

 ▷ The number of nodes in the list is in the range [1, 105].

 ▷ 0 <= Node.val <= 9

 

Example:

Input: head = [1,2,2,1]
Output: true

 

 처음에는 단일연결리스트를 파이썬 리스트로 옮기고 짝수/홀수 인 경우를 나눠 반반 또 리스트에 나눠 담어 한 리스트를 뒤집은 뒤에 두개가 같은지 비교하려 했다. 하지만 문제에서 구현된 싱리스트의 동작을 이해를 위해 첫 문제는 답을 보고 풀었다. 코드만 봐도 아이디어가 비슷해서 어떻게 동작하는 지 이해가 되었다.

# 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:
        
        q = collections.deque()
        
        if not head:
            return True
        
        node = head
        
        # change to python list
        while node is not None:
            q.append(node.val)
            node = node.next
        
        # check if it's palindrome
        while len(q) > 1:
            if q.popleft() != q.pop():
                return False
        
        return True

 파이썬 리스트는 동적 배열로 이루어져 pop(0)을 하면 O(n) 만큼 시간이 걸린다. 파이썬 deque는 이중연결리스트로 구성돼있어 popleft를 하면 O(1) 안에 동작이 이루어져 훨씬 속도가 빨라 deque로 변경했다. 이 문제에서는 리스트 개념을 잘 이해하고 있고 파이썬의 자료 구조가 이론에 어떤 자료 구조와 매칭되는지 알고 리스트 양 끝을 꺼내서 비교하는 아이디어만 있다면 쉽게 풀 수 있었던 문제인 것 같다.