check if a linked list is a palindrome args head the head of the linked list returns bool true if the linked list is a palindrome false otherwise examples ispalindromenone true ispalindromelistnode1 true ispalindromelistnode1 listnode2 false ispalindromelistnode1 listnode2 listnode1 true ispalindromelistnode1 listnode2 listnode2 listnode1 true split the list to two parts slow will always be defined adding this check to resolve mypy static check reverse the second part compare two parts second part has the same or one less node check if a linked list is a palindrome using a stack args head listnode the head of the linked list returns bool true if the linked list is a palindrome false otherwise examples ispalindromestacknone true ispalindromestacklistnode1 true ispalindromestacklistnode1 listnode2 false ispalindromestacklistnode1 listnode2 listnode1 true ispalindromestacklistnode1 listnode2 listnode2 listnode1 true 1 get the midpoint slow slow will always be defined adding this check to resolve mypy static check 2 push the second half into the stack 3 comparison check if a linked list is a palindrome using a dictionary args head listnode the head of the linked list returns bool true if the linked list is a palindrome false otherwise examples ispalindromedictnone true ispalindromedictlistnode1 true ispalindromedictlistnode1 listnode2 false ispalindromedictlistnode1 listnode2 listnode1 true ispalindromedictlistnode1 listnode2 listnode2 listnode1 true ispalindromedict listnode 1 listnode2 listnode1 listnode3 listnode2 listnode1 false check if a linked list is a palindrome args head the head of the linked list returns bool true if the linked list is a palindrome false otherwise examples is_palindrome none true is_palindrome listnode 1 true is_palindrome listnode 1 listnode 2 false is_palindrome listnode 1 listnode 2 listnode 1 true is_palindrome listnode 1 listnode 2 listnode 2 listnode 1 true split the list to two parts slow will always be defined adding this check to resolve mypy static check don t forget here but forget still works reverse the second part compare two parts second part has the same or one less node check if a linked list is a palindrome using a stack args head listnode the head of the linked list returns bool true if the linked list is a palindrome false otherwise examples is_palindrome_stack none true is_palindrome_stack listnode 1 true is_palindrome_stack listnode 1 listnode 2 false is_palindrome_stack listnode 1 listnode 2 listnode 1 true is_palindrome_stack listnode 1 listnode 2 listnode 2 listnode 1 true 1 get the midpoint slow slow will always be defined adding this check to resolve mypy static check 2 push the second half into the stack 3 comparison check if a linked list is a palindrome using a dictionary args head listnode the head of the linked list returns bool true if the linked list is a palindrome false otherwise examples is_palindrome_dict none true is_palindrome_dict listnode 1 true is_palindrome_dict listnode 1 listnode 2 false is_palindrome_dict listnode 1 listnode 2 listnode 1 true is_palindrome_dict listnode 1 listnode 2 listnode 2 listnode 1 true is_palindrome_dict listnode 1 listnode 2 listnode 1 listnode 3 listnode 2 listnode 1 false
from __future__ import annotations

from dataclasses import dataclass


@dataclass
class ListNode:
    val: int = 0
    next_node: ListNode | None = None


def is_palindrome(head: ListNode | None) -> bool:
    
    if not head:
        return True
    
    fast: ListNode | None = head.next_node
    slow: ListNode | None = head
    while fast and fast.next_node:
        fast = fast.next_node.next_node
        slow = slow.next_node if slow else None
    if slow:
        
        
        second = slow.next_node
        slow.next_node = None  
    
    node: ListNode | None = None
    while second:
        nxt = second.next_node
        second.next_node = node
        node = second
        second = nxt
    
    
    while node and head:
        if node.val != head.val:
            return False
        node = node.next_node
        head = head.next_node
    return True


def is_palindrome_stack(head: ListNode | None) -> bool:
    
    if not head or not head.next_node:
        return True

    
    slow: ListNode | None = head
    fast: ListNode | None = head
    while fast and fast.next_node:
        fast = fast.next_node.next_node
        slow = slow.next_node if slow else None

    
    
    if slow:
        stack = [slow.val]

        
        while slow.next_node:
            slow = slow.next_node
            stack.append(slow.val)

        
        cur: ListNode | None = head
        while stack and cur:
            if stack.pop() != cur.val:
                return False
            cur = cur.next_node

    return True


def is_palindrome_dict(head: ListNode | None) -> bool:
    
    if not head or not head.next_node:
        return True
    d: dict[int, list[int]] = {}
    pos = 0
    while head:
        if head.val in d:
            d[head.val].append(pos)
        else:
            d[head.val] = [pos]
        head = head.next_node
        pos += 1
    checksum = pos - 1
    middle = 0
    for v in d.values():
        if len(v) % 2 != 0:
            middle += 1
        else:
            step = 0
            for i in range(len(v)):
                if v[i] + v[len(v) - 1 - step] != checksum:
                    return False
                step += 1
        if middle > 1:
            return False
    return True


if __name__ == "__main__":
    import doctest

    doctest.testmod()