[LeetCode] Palindrome Linked List

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

Palindrome Linked List - LeetCode

 

Deque를 활용하면 popleft도 O(1) 이므로 성능 향상

# 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: Optional[ListNode]) -> bool:
        q : Deque = collections.deque()
        
        if head is None:
            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

 

런너를 이용

1. fast는 연결 리스트를 두 칸씩 뛰고, slow는 한 칸씩 뛴다.

2. fast가 끝점에 도착하면 slow는 연결 리스트의 중앙에 오게 된다.

3. slow가 앞으로 나아가면 reverse를 만들어서 뒤로 이동하게 끔 생성

4. 탐색을 마치면 slow 와 rev를 비교하며 팰린드롬인지 검사.

def isPalindrome(self, head: Optional[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