# Python3 program to check if
# linked list is palindrome
class Node:
    def __init__(self, d):
        self.data = d
        self.next = None

# Function to reverse a linked list
def reverse(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

# Function to check if two lists are identical
def isIdentical(n1, n2):
    while n1 and n2:
        if n1.data != n2.data:
            return False
        n1 = n1.next
        n2 = n2.next
    return True

# Function to check whether the list is palindrome
def isPalindrome(head):
    if head is None or head.next is None:
        return True

    right, Left = head, head

    # Find the middle of the list
    while Left.next and Left.next.next:
        right = right.next
        Left = Left.next.next

    # Split the list and reverse the second half
    head2 = reverse(right.next)
    right.next = None

    # Check if the two halves are identical
    ret = isIdentical(head, head2)

    # Restore the original list
    head2 = reverse(head2)
    right.next = head2

    return ret

if __name__ == "__main__":
  
    # Linked list : 1->2->3->2->1
    head = Node(1)
    head.next = Node(2)
    head.next.next = Node(3)
    head.next.next.next = Node(2)
    head.next.next.next.next = Node(1)

    result = isPalindrome(head)

    if result:
        print("true")
    else:
        print("false")