import java.util.*;
public class LinkedList {
public static class Node{
int data;
Node next;
public Node (int data) {
this.data = data;
this.next = null;
}
}
public static Node head;
public static Node tail;
public static int size;
public void addFirst(int data){
Node newNode=new Node(data);
size++;
if(head==null){
head=tail=newNode;
return;
}
newNode.next=head;
head=newNode;
}
public void addLast(int data){
Node newNode= new Node(data);
tail.next=newNode;
newNode.next=null;
tail=newNode;
}
public void add(int idx, int data){
if(idx==0){
addFirst(data);
}
else{
Node newNode=new Node(data);
size++;
Node temp=head;
int i=0;
while(i<idx-1){
temp=temp.next;
i++;
}
newNode.next=temp.next;
temp.next=newNode;
}
}
public void printLL(LinkedList ll){
Node temp=ll.head;
while(temp!=null){
System.out.print(temp.data + "->");
temp=temp.next;
}
System.out.println("null");
}
public Node findMid(Node head){
Node slow=head;
Node fast=head;
while(fast!=null && fast.next!=null){
slow=slow.next;
fast=fast.next.next;
}
return slow;
}
public boolean checkPalindrome(){
if(head==null || head.next==null) return true;
Node midNode=findMid(head);
Node prev=null;
Node curr=midNode;
Node next;
while(curr!=null){
next=curr.next;
curr.next=prev;
prev=curr;
curr=next;
}
Node right=prev;
Node left=head;
while(right!=null){
if(left.data!=right.data) return false;
left = left.next;
right=right.next;
}
return true;
}
public static void main(String[] args){
LinkedList ll = new LinkedList();
ll.addFirst(1);
ll.addLast(2);
ll.addLast(3);
ll.addLast(1);
ll.add(3,2);
//ll.printLL(ll);
System.out.println(ll.checkPalindrome());
}
}
