class node:
    def __init__(self, data=None):
        self.data = data
        self.next = None


class linked_list:

    def __init__(self):
        self.head = None

    def insertBeg(self, data):
        temp = node(data)
        temp.next = self.head
        self.head = temp
        
    def compareList(self, headA , headB):
        while headA and headB and (headA.data == headB.data):
            headA = headA.next
            headB = headB.next
        return 1 if headA==headB else 0

    def pallindrome(self,first_head,first_end,second_head,second_end):
    	if self.length()== 1:
    		print('Pallindrome')
    		return
    	first_end.next = None
    	second_reverselist_head = self.reverse_list(second_head)
    	res = self.compareList(first_head,second_reverselist_head)
    	print("Pallindrome") if (res == 1) else print("Not Pallindrome")    # python conditonal statement(ternary)
    	
    def printList(self, head):
	    p = head
	    while p:
	        print(p.data, end=' ')
	        if p.next is not None:
	            print('->', end=' ')
	        p = p.next
	    print()

    def reverse_list(self, head):
        if head is None or head.next is None :
            return head
        res = self.reverse_list(head.next)
        head.next.next = head
        head.next = None
        return res

    def middle_node(self):
	    x = self.length() % 2  # check even-odd list
	    p = self.head
	    c = 1
	    if self.length()==1:   
	    	return self.head,self.head,self.head,self.head
	    	
	    # end pointer for second list
	    last = self.head
	    while last.next:
	        last = last.next

	    while p:
	        if x != 0:	 # odd list
	            if (self.length() // 2) == c:
	                # return first and last node of both the list
	                return self.head, p, p.next.next, last	 # drop middle element(p.next) for odd list
	            c += 1
	            p = p.next

	        elif x == 0:  # even list
	            if self.length() // 2 == c:
	                # return first and last node of both the list
	                return self.head, p, p.next, last	
	            c += 1
	            p = p.next

    def length(self):
	    p = self.head
	    c = 0
	    while p:
	        c += 1
	        p = p.next
	    return c



l = linked_list()
l.insertBeg(9)
l.insertBeg(4)
l.insertBeg(5)
l.insertBeg(2)
l.insertBeg(7)
l.insertBeg(2)
l.insertBeg(5)
l.insertBeg(4)
l.insertBeg(9)
print("\nnode length is {} ".format(l.length()))
print('list is....')
l.printList(l.head)
first_head,first_end, second_head,second_end= l.middle_node()
l.pallindrome(first_head,first_end, second_head,second_end)
print()