[Python] Leet Code 234. Palindrome Linked List

본 내용은 <파이썬 알고리즘 인터뷰>를 참고했습니다.

리스트 변환

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:

        q: List = []

        if not head:
            return True

        node = head
        while node:
            q.append(node.val)
            node = node.next

        while len(q) > 1:
            if q.pop(0) != q.pop():
                return False

        return True

이 문제에서 배워야할 포인트

• 일반 list에서의 popleft : .pop(0)
  • 느림

데크를 이용한 최적화

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:

        q: Deque = 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

이 문제에서 배워야할 포인트

• deque 선언 : collections.deque()
• deque : .popleft(), .pop()
  • 빠르다

런너를 이용한 우아한 풀이

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:

        rev = None
        slow = fast = head
        while fast and fast.next:
            rev, rev.next, slow, fast = slow, rev, slow.next, fast.next.next

        if fast:
            slow = slow.next

        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next
        return not rev

이 문제에서 배워야할 포인트

• 파이썬 다중 할당
  • 다중 할당 하지 않으면 에러!
• 홀수일 때, slow를 한 번 더 건너게 함