[Q. 13] 팰린드롬 연결 리스트

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

 

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

 

위의 코드가 문제에서 제시한 연결 리스트이다. val 은 현재 노드의 값, next는 다음 노드를 가리키는 것이다.

먼저 연결 리스트를 팰린드롬인지 확인하기 위해서는 자료형을 변경해야한다. 파이썬에는 deque라는 자료구조가 있다. deque는 리스트와 같지만 append와 pop을 리스트 마지막이 아닌 처음에서도 할 수 있다는 특징이 있다.

 

먼저, 해당 연결 리스트를 deque 자료형으로 변경한다.

queue = deque()

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

 

그 다음은, dequeue의 처음과 마지막 값을 뽑아 같은지 비교하며 다를 경우 False 값을 return 한다.

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

 

while 조건은 큐가 홀수 길이 일 수도 있으므로 len(queue) > 1로 설정하였다.

 

전체 코드는 다음과 같다.

# 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:

        queue = deque()

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

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

        return True