C2P7.java

package chapter2;

import java.util.LinkedList;

/*
 * Career Cup 2.7
 * Implement a function to check if a linked list is a palindrome.
 */
public class C2p7 {
  
	/*
	 * first calculate the length of the linked list
	 * then push the former half of the linked list into a stack, then check its equality with later half
	 * time: O(n), space:O(n)
	 */
	public static boolean isPalindrome(Node head) {
		LinkedList<Integer> stack = new LinkedList<Integer>();
		int length = 0;
		Node pointer = head;
		while (pointer != null) {
			length++;
			pointer = pointer.next;
		}
		pointer = head;
		for (int i = 0; i < length / 2; i++) {
			stack.push(pointer.value);
			pointer = pointer.next;
		}
		if (length % 2 == 1) {
			pointer = pointer.next;
		}
		while (pointer != null) {
			if (pointer.value != stack.pop())
				return false;
			pointer = pointer.next;
		}
		return true;

	}

	public static void main(String[] args) {
		int[] array1 = { 1, 2, 3, 4, 3, 2, 1 };
		int[] array2 = { 1, 2, 2, 1 };
		int[] array3 = { 1, 2, 3, 2, 3 };
		Node head1 = new Node(array1);
		Node head2 = new Node(array2);
		Node head3 = new Node(array3);
		System.out.println(isPalindrome(head1));
		System.out.println(isPalindrome(head2));
		System.out.println(isPalindrome(head3));

	}

}