import java.util.*;
public class LinkedList {
private class Node {
int data;
Node next;
Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
private Node head;
private Node tail;
private int size;
public LinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
public LinkedList(Node head, Node tail, int size) {
this.head = head;
this.tail = tail;
this.size = size;
}
// O(1)
public int size() {
return this.size;
}
// O(1)
public boolean isEmpty() {
return this.size() == 0;
}
// O(1)
public Node getFirst() throws Exception {
if (this.isEmpty()) {
throw new Exception("List is empty.");
}
return this.head;
}
// O(1)
public int getLast() throws Exception {
if (this.isEmpty()) {
throw new Exception("List is empty.");
}
return this.tail.data;
}
// O(N)
public int getAt(int idx) throws Exception {
Node temp = this.getNodeAt(idx);
return temp.data;
}
// O(N)
private Node getNodeAt(int idx) throws Exception {
if (this.isEmpty()) {
throw new Exception("List is empty");
}
if (idx < 0 || idx >= this.size()) {
throw new Exception("Invalid arguments");
}
Node retVal = this.head;
for (int i = 0; i < idx; i++) {
retVal = retVal.next;
}
return retVal;
}
// O(1)
public void addFirst(int data) {
Node node = new Node(data, this.head);
if (this.size() == 0) {
this.head = node;
this.tail = node;
} else {
this.head = node;
}
this.size++;
}
// O(1)
public void addLast(int data) {
Node node = new Node(data, null);
if (this.size() == 0) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.size++;
}
// O(n)
public void addAt(int idx, int data) throws Exception {
if (idx < 0 || idx > this.size()) {
throw new Exception("Invalid arguments");
}
if (idx == 0) {
this.addFirst(data);
} else if (idx == this.size()) {
this.addLast(data);
} else {
Node nm1 = this.getNodeAt(idx - 1);
Node n = nm1.next;
Node node = new Node(data, n);
nm1.next = node;
this.size++;
}
}
// O(1)
public int removeFirst() throws Exception {
if (this.isEmpty()) {
throw new Exception("List is empty");
}
int retVal = this.head.data;
if (this.size() == 1) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
}
this.size--;
return retVal;
}
// O(n)
public int removeLast() throws Exception {
if (this.isEmpty()) {
throw new Exception("List is empty");
}
int retVal = this.tail.data;
if (this.size() == 1) {
this.head = null;
this.tail = null;
} else {
Node sm2 = this.getNodeAt(this.size() - 2);
sm2.next = null;
this.tail = sm2;
}
this.size--;
return retVal;
}
// O(n)
public int removeAt(int idx) throws Exception {
if (this.isEmpty()) {
throw new Exception("List is empty");
}
if (idx < 0 || idx >= this.size()) {
throw new Exception("Invalid arguments");
}
if (idx == 0) {
return this.removeFirst();
} else if (idx == this.size() - 1) {
return this.removeLast();
} else {
Node nm1 = this.getNodeAt(idx - 1);
Node n = nm1.next;
Node np1 = n.next;
nm1.next = np1;
this.size--;
return n.data;
}
}
// O(n)
public void display() {
Node node = this.head;
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
//System.out.println("END");
}
boolean isPalindrome(Node head)
{
Node slow_ptr = head;
Node fast_ptr = head;
Node prev_of_slow_ptr = head;
Node midnode = null; // To handle odd size list
boolean res = true; // initialize result
if (head != null && head.next != null) {
/* Get the middle of the list. Move slow_ptr by 1
and fast_ptrr by 2, slow_ptr will have the middle
node */
while (fast_ptr != null && fast_ptr.next != null) {
fast_ptr = fast_ptr.next.next;
/*We need previous of the slow_ptr for
linked lists with odd elements */
prev_of_slow_ptr = slow_ptr;
slow_ptr = slow_ptr.next;
}
/* fast_ptr would become NULL when there are even elements
in the list and not NULL for odd elements. We need to skip
the middle node for odd case and store it somewhere so that
we can restore the original list */
if (fast_ptr != null) {
midnode = slow_ptr;
slow_ptr = slow_ptr.next;
}
// Now reverse the second half and compare it with first half
Node second_half = slow_ptr;
prev_of_slow_ptr.next = null; // NULL terminate first half
reverse(second_half); // Reverse the second half
res = compareLists(head, second_half); // compare
/* Construct the original list back */
reverse(second_half); // Reverse the second half again
if (midnode != null) {
// If there was a mid node (odd size case) which
// was not part of either first half or second half.
prev_of_slow_ptr.next = midnode;
midnode.next = second_half;
}
else
prev_of_slow_ptr.next = second_half;
}
return res;
}
/* Function to reverse the linked list Note that this
function may change the head */
void reverse(Node second_half)
{
Node prev = null;
Node current = second_half;
Node next;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
second_half = prev;
}
/* Function to check if two input lists have same data*/
boolean compareLists(Node head1, Node head2)
{
Node temp1 = head1;
Node temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.data == temp2.data) {
temp1 = temp1.next;
temp2 = temp2.next;
}
else
return false;
}
/* Both are empty reurn 1*/
if (temp1 == null && temp2 == null)
return true;
/* Will reach here when one is NULL
and other is not */
return false;
}
/* Push a node to linked list. Note that this function
changes the head */
public void push(char new_data)
{
/* Allocate the Node &
Put in the data */
Node new_node = new Node(new_data);
/* link the old list off the new one */
new_node.next = head;
/* Move the head to point to new Node */
head = new_node;
}
// A utility function to print a given linked list
void printList(Node ptr)
{
while (ptr != null) {
System.out.print(ptr.data + "->");
ptr = ptr.next;
}
System.out.println("NULL");
}
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int N = scn.nextInt();
LinkedList list = new LinkedList();
for (int i = 0; i < N; i++) {
list.addLast(scn.nextInt());
}
Node head = list.getFirst();
System.out.println(list.isPalindrome(head));
}
}