[LeetCode] 234. Palindrome Linked List

1. 문제

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

Palindrome Linked List - LeetCode

2. 접근 방법

deque를 이용해서 풀었습니다.

저번에두 팰린드롬 문제 풀 때 deque를 사용해서 popleft()와 pop()을 비교해서 풀었는데, 동일한 방법으로 풀었습ㄴ다.

 

하지만 이 문제는 주어진 input값이 연결리스트 형태이기 때문에 value만 데크 자료형에 담아줍니다.

 

1. 일단 q라는 데크 자료형 변수를 하나 만들어줍니다.

 

2. 만약 input값이 존재하지 않는다면 => 팰린드롬이 맞기 때문에 바로 return을 합니다.

 

3. input값이 존재한다면, input 값들을 모두 q에 담습니다.

 

4. q에 담긴 것들을 양쪽 끝에서부터 비교를 하며 만약 양쪽 끝이 일치하지 않는 경우 바로 False를 반환합니다.

 

5. 양쪽 끝을 모두 비교했다면, 팰린드롬이 맞으므로 True를 반환합니다.

3. 코드

python

# 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:
        q = collections.deque()
        
        if not head:
            return True
        
        node = head
        while node:
            q.append(node.val)
            node = node.next
            
        while len(q) > 1:
            if q.popleft() != q.pop():
                return False
        
        return True

4. 마치며

사실 q를 데크가 아닌 리스트로 선언할 수 있지만, 

파이썬의 리스트는 동적 배열이라 첫번째 요소를 가져올 경우 (q.pop(0))

모든 값이 한 칸씩 시프팅되어 시간 복잡도 O(n)이 발생하게 됩니다.

 

하지만 데크는, 이중 연결 리스트 구조이기 때문에 양쪽 방향 모두 추출하는 데 시간 복잡도 O(1)이 실행되기 때문에,

이 문제에서는 데크로 선언하여 문제 풀이를 진행했습니다.

 

위의 경우가 q를 리스트로 선언했을 때, 아래의 경우가 데크로 선언했을 때