[Leetcode]234. Palindrome Linked List

Palindrome Linked List - LeetCode

Palindrome Linked List - LeetCode

데크를 이용한 풀이

리스트로 변환하여 pop(0)를 이용해 문제를 해결할 수 있지만 최적화를 위해 deque 를 사용

def isPalindrome2(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

런너를 이용한 풀이

이 문제의 의도에 맞는 가장 정확한 풀이라고 할 수 있다.

fast는 slow가 1칸 전진할 때 2칸전진한다 slow 는 전진하면서 역순으로 리스트를 저장한다.

노드가 짝수개인 경우를 주의하자

def isPalindrome(self, head: ListNode) -> bool:
        rev = None
        slow = fast = head

        while fast and fast.next:
            fast = fast.next.next
            rev, rev.next, slow = slow , rev,slow.next
        if fast:
            slow = slow.next

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

다중할당 시 주의할점

위 문제에서

 rev, rev.next, slow = slow , rev,slow.next

가 아닌

rev, rev.next = slow, rev
slow = slow.next

이런식으로 수정하면 오류가 발생한다.

그 이유는 rev = slow 구문에서 slow의 구조까지 변경되어 버리기때문이다.

slow = slow.next 도 한번에 실행 해주어야 오류가 발생하지않는다.