234. Palindrome Linked List

리스트로 변환

class Solution:
    def isPalindrome(self, head):

        li = []
        while(head):
            li.append(head.val)

            head = head.next

        while li:
            # 처음부터 하나만 있거나 다 빠지고 하나만 있으면 팰린드롬임.
            if len(li) == 1:
                return True

            if li.pop(0) != li.pop():
                return False

        return True

교재 답

- deque

파이썬 데크는 이중 연결 리스트여서 리스트 맨 앞꺼 빼도 시간 O(1)임.

import collections

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # 데크 자료형 선언
        q = collections.deque()

        if not head:
            return True

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

        while q:
            # 처음부터 하나만 있거나 체크 다해서 빠지고 하나만 있으면 팰린드롬임.
            if len(q) == 1:
                return True


            # 데크라서 리스트랑 다르게 왼쪽꺼 빼는데 시간 O(1) 걸림
            if q.popleft() != q.pop():
                return False

        return True

- 러너 사용

슬로우 러너는 연결 리스트 한 칸씩 이동하고 패스트 러너는 연결 리스트를 슬로우 러너의 2배인 2칸씩 이동해서 패스트 러너가 끝에 도달하면 슬로우 러너는 연결 리스트의 한가운데에 도달함.
따라서 슬로우 러너가 이동하면서 리스트의 왼쪽 절반을 뒤집고 이 뒤집힌 왼쪽 절반이랑 정상적인 오른쪽 절반(슬로우 러너가 시작점임)이랑 비교하면됨.

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # 슬로우 러너가 지나간 곳을 역순으로 리스트 만들어줌.
        reverse = None

        slow = fast = head

        while fast and fast.next:
            # fast runner 이동
            fast = fast.next.next
            # 한 번에 다중할당해야지 그대로 적용됨
            # rev, rev.next = slow, rev
            # slow = slow.next
            # 처럼 나눠쓰면 첫 줄에서 rev = slow여서 rev.next가 slow의 next를 바꿔버리기 때문에 의도한것처럼 안됨.
            reverse, reverse.next, slow = slow, reverse, slow.next

        # 리스트 길이가 홀수면 팰린드롬 체크할떄 가운데는 안 세야하니 슬로우가 한칸 더 가야함.
        if fast:
            slow = slow.next

        while reverse and reverse.val == slow.val:
            slow, reverse = slow.next, reverse.next

        # reverse가 남았으면 팰린드롬이 아닌거임.
        return not reverse

문제