LEETCODE - Palindrome Linked List

collections을 이용

from typing import List, Deque
import collections

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalidrome(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(): # pop(0) 맨 앞, pop() 맨 뒤
            return False
# 연결 리스트에서 pop(0)을 하면 모든 값이 한 칸씩 shifting되며 시간 복잡도 O(n)이 발생한다.
# Deque는 이중 연결 리스트 구조로 양쪽 방향 모두 추출하는 데 시간 복잡도 O(1)에 실해된다.
def isPalidrome_deque(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

Runner 기법을 사용

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