[Algorithms] 파이썬 알고리즘 인터뷰 #13, LeetCode 234번: Palindrome Linked List

연결리스트 단원의 첫번째 문제다. 연결리스트가 팰린드롬 구조인지 판단하는 문제인데 책에서는 3가지 풀이법을 제시한다. 1.연결리스트를 리스트로 변환하는 방법 , 2. Deque를 활용하는 방법, 3.Runner을 활용한 풀이를 제시하는데 그중에 난 2번 만 정리해 두려고한다. 3번 너무 귀찮아요ㅋ

 

Deque를 이용한 최적화

 

Deque의 장점의 popleft와 pop을 이용해서 양 끝단의 값을 손쉽게 받을 수 있다는 것이다. 이런 팰린드롬 여부를 확인하는 문제를 해결 할때 딱일거같다. 

 

# 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:
    	# Deque 선언
        q: Deque = collections.deque()
        
        # 빈 연결리스트는 팰린드롬이다
        if not head:
            return True
        
        node = head
        
        # deque인 q에 연결리스트를 복사해 준다. 
        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

 

간단하게 deque를 이용해서 해결할수 있다!