leetcode 234. Palindrome Linked List 리트코드 234. 팰린드롬 연결 리스트 문제 풀이

<파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 풀이한 포스팅이다.

 

문제는 모두 리트코드에 출제된 문제들이며, 직접 풀었지만, 책에서 주는 힌트와 풀이 과정들을 참고한 경우가 많다.

이곳은  정리한 책에 나온 문제에 대한 목록과 해설을 정리한 공식 깃허브 페이지 이며, 

다음 포스팅은 내가 푼 <파이썬 알고리즘 인터뷰> 문제 풀이 목록을 정리해 놓았다.

 

문제

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

Palindrome Linked List - LeetCode

입력: 연결 리스트

출력: 불린(True or False)

 

문제 요약: 주어진 연결리스트가 팰린드롬이면 True 아니면 False 를 출력

유의 사항: 노드 크기가 10**5까지 이기 때문에 효율성을 고려해야 한다.

생각 과정

주어진 head가 리스트가 아니라 연결 리스트라는 걸 잘 기억해야 한다.

1->2->2->1

에서, 1,2,2,1은 노드의 value 값이다.

 

collections 라이브러리를 import하면 deque 자료형을 사용할 수 있는데,

deque는 LIFO인 .pop() 뿐 아니라,  .popleft()라는 FIFO 메서드도 지원한다.그래서 

while len(q)>1: (꼭 1보다 커야 한다 왜냐면 홀수인 경우 마지막에 하나 남기 때문에)

q.popleft() == q.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: ListNode) -> bool:
        # 데이터 타입 deque로
        q: Deque = collections.deque()
            
        node = head 
        if not head:
            return True
        
        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