# تعريف العقدة في القائمة المترابطة
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# دالة للتحقق مما إذا كانت القائمة Palindrome
def isPalindrome(head: ListNode) -> bool:
    # الخطوة 1: العثور على منتصف القائمة باستخدام مؤشرين (بطيء وسريع)
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # الخطوة 2: عكس النصف الثاني من القائمة
    prev = None
    while slow:
        next_node = slow.next
        slow.next = prev
        prev = slow
        slow = next_node

    # الخطوة 3: مقارنة النصف الأول مع النصف الثاني المعكوس
    left, right = head, prev
    while right:  # نقارن النصف الأول مع النصف المعكوس فقط
        if left.val != right.val:
            return False
        left = left.next
        right = right.next

    return True

# دالة لإنشاء قائمة مترابطة من قائمة أرقام
def createLinkedList(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

# قراءة إدخال المستخدم مع التحقق
while True:
    user_input = input("أدخل القيم (مفصولة بمسافات، على سبيل المثال: 1 2 2 1): ")
    try:
        values = list(map(int, user_input.split()))
        break  # إذا كان الإدخال صحيحًا، نخرج من الحلقة
    except ValueError:
        print("يرجى إدخال الأرقام فقط مفصولة بمسافات بدون أقواس أو فواصل. حاول مرة أخرى.")

# إنشاء القائمة المترابطة
head = createLinkedList(values)

# التحقق مما إذا كانت القائمة Palindrome
result = isPalindrome(head)

# طباعة النتيجة
print("هل القائمة Palindrome؟", result)