import java.util.Stack;

public class IsPalindromeList {

public static class Node {

public int value;

public Node next;

public Node(int data) {

this.value = data;

}

}

// need n extra space: Stack

public static boolean isPalindrome1(Node head) {

Stack<Node> stack = new Stack<Node>();

Node curr = head;

while (curr != null) {

stack.push(curr);

curr = curr.next;

}

while (head != null) {

if (stack.pop().value != head.value) {

return false;

}

head = head.next;

}

return true;

}

// need n/2 extra space: Stack(放链表后半段)

public static boolean isPalindrome2(Node head) {

if (head == null || head.next == null) {

return true;

}

Node right = head.next;

Node curr = head;

while ((curr.next != null) && (curr.next.next != null)) {

right = right.next;

curr = curr.next.next;

}

Stack<Node> stack = new Stack<Node>();

while (right != null) {

stack.push(right);

right = right.next;

}

while (!stack.isEmpty()) {

if (head.value != stack.pop().value) {

return false;

}

head = head.next;

}

return true;

}

// need O(1) extra space

public static boolean isPalindrome3(Node head) {

if (head == null || head.next == null) {

return true;

}

Node n1 = head; //slow node

Node n2 = head; //fast node

while ((n2.next != null) && (n2.next.next != null)) {

n1 = n1.next; //mid

n2 = n2.next.next; //end

}

n2 = n1.next; //right part first node

n1.next = null; //mid.next = null

Node n3 = null;

while (n2 != null) {

n3 = n2.next;

n2.next = n1;

n1 = n2;

n2 = n3;

}

n3 = n1; //n3->save last node (for recovery)

n2 = head; // n2->left first node

boolean res = true;

while ((n1 != null) && (n2 != null)) {

if (n1.value != n2.value) {

res = false;

break;

}

n1 = n1.next; //left to mid

n2 = n2.next; //right to mid

}

// recover list

n1 = n3.next;

n3.next = null;

while (n1 != null) {

n2 = n1.next;

n1.next = n3;

n3 = n1;

n1 = n2;

}

return res;

}

public static void printLinkedList(Node head) {

System.out.println("Linked List: ");

while (head != null) {

System.out.print(head.value + " ");

head = head.next;

}

System.out.println();

}

public static void main(String[] args) {

Node head = null;

printLinkedList(head);

System.out.print(isPalindrome1(head) + " | ");

System.out.print(isPalindrome2(head) + " | ");

System.out.println(isPalindrome3(head) + " | ");

printLinkedList(head);

System.out.println("=========================");

head = new Node(1);

printLinkedList(head);

System.out.print(isPalindrome1(head) + " | ");

System.out.print(isPalindrome2(head) + " | ");

System.out.println(isPalindrome3(head) + " | ");

printLinkedList(head);

System.out.println("=========================");

head = new Node(1);

head.next = new Node(2);

printLinkedList(head);

System.out.print(isPalindrome1(head) + " | ");

System.out.print(isPalindrome2(head) + " | ");

System.out.println(isPalindrome3(head) + " | ");

printLinkedList(head);

System.out.println("=========================");

head = new Node(1);

head.next = new Node(1);

printLinkedList(head);

System.out.print(isPalindrome1(head) + " | ");

System.out.print(isPalindrome2(head) + " | ");

System.out.println(isPalindrome3(head) + " | ");

printLinkedList(head);

System.out.println("=========================");

head = new Node(1);

head.next = new Node(2);

head.next.next = new Node(3);

printLinkedList(head);

System.out.print(isPalindrome1(head) + " | ");

System.out.print(isPalindrome2(head) + " | ");

System.out.println(isPalindrome3(head) + " | ");

printLinkedList(head);

System.out.println("=========================");

head = new Node(1);

head.next = new Node(2);

head.next.next = new Node(1);

printLinkedList(head);

System.out.print(isPalindrome1(head) + " | ");

System.out.print(isPalindrome2(head) + " | ");

System.out.println(isPalindrome3(head) + " | ");

printLinkedList(head);

System.out.println("=========================");

head = new Node(1);

head.next = new Node(2);

head.next.next = new Node(3);

head.next.next.next = new Node(1);

printLinkedList(head);

System.out.print(isPalindrome1(head) + " | ");

System.out.print(isPalindrome2(head) + " | ");

System.out.println(isPalindrome3(head) + " | ");

printLinkedList(head);

System.out.println("=========================");

head = new Node(1);

head.next = new Node(2);

head.next.next = new Node(2);

head.next.next.next = new Node(1);

printLinkedList(head);

System.out.print(isPalindrome1(head) + " | ");

System.out.print(isPalindrome2(head) + " | ");

System.out.println(isPalindrome3(head) + " | ");

printLinkedList(head);

System.out.println("=========================");

head = new Node(1);

head.next = new Node(2);

head.next.next = new Node(3);

head.next.next.next = new Node(2);

head.next.next.next.next = new Node(1);

printLinkedList(head);

System.out.print(isPalindrome1(head) + " | ");

System.out.print(isPalindrome2(head) + " | ");

System.out.println(isPalindrome3(head) + " | ");

printLinkedList(head);

System.out.println("=========================");

}

}