[연결 리스트] 팰린드롬 연결 리스트

 

234 | Palindrome Linked List
https://leetcode.com/problems/palindrome-linked-list/

 

 

 

이상 코드

 

 

리스트 변환

 

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        q: List = []

        if not head:
            return True

        node = head
        # 리스트 변환
        while node is not None:
            q.append(node.val)
            node = node.next

        # 팰린드롬 판별
        while len(q) > 1:
            if q.pop(0) != q.pop():
                return False

        return True

 

 

 

데크를 이용한 최적화

 

 

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # 데크 자료형 선언
        q: Deque = collections.deque()

        if not head:
            return True

        node = head
        while node is not None:
            q.append(node.val)
            node = node.next

        while len(q) > 1:
            if q.popleft() != q.pop():
                return False

        return True

 

 

• list에서 pop(0) 은 시간 복잡도 O(N)
• deque를 이용하면 popleft()이 pop(0)과 같은 역할을 하지만 시간 복잡도 O(1)