[Python] Leetcode 234. 팰린드롬 연결 리스트

in Algorithm on 문제풀이, 자료구조, Linkedlist


Leetcode 234 팰린드롬 연결 리스트

문제

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

Parlindrome Linked List1

입력

head = [1,2,2,1]

출력

True

풀이

1. 리스트 변환

  • 팰린드롬 여부를 판별하기 위해서는 앞뒤로 모두 추출할 수 있는 자료구조가 필요하다.
  • 파이썬의 리스트는 pop()함수에 인덱스를 지정할 수 있어 마지막 요소가 아니라도 얼마든지 원하는 위치를 자유롭게 추출할 수 있다.
  • q.pop(0) 에서 시간 복잡도가 O(N)이 발생한다.
# node4 = ListNode(4)          # 마지막 노드 (next가 None)
# node3 = ListNode(3, node4)   # node3의 next가 node4를 가리킴
# node2 = ListNode(2, node3)   # node2의 next가 node3을 가리킴
# node1 = ListNode(1, node2)   # node1의 next가 node2를 가리킴

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

2. deque를 이용한 최적화

  • 맨 앞의 데이터를 가져올 떄 O(n) 이내에 처리할 수 있는 자료형이 필요하다.
  • 파이썬의 데크는 이중 연결 리스트 구조로 양쪽 방향 모두 추출하는데 시간 복잡도 O(1)에 실행된다.
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