Q2_7.java

import java.util.Stack;

public class Q2_7{	
	public static void main(String args[]){
		Q2_7  test = new Q2_7();
		
		LLNode head = new LLNode("1",null);
		
		head.next = new LLNode("1",new LLNode("3", new LLNode("2",new LLNode("1", null))));
		
		System.out.println(isPalindromeRecursive(head,5).isPalindrome);
		System.out.println(isPalindromeStack(head));
		System.out.println(isPalindromeReverse(head));
		while(head!=null){
			System.out.println(head.data);
			head= head.next;
		}
	
	}
	
	// use a stack to store the first half nodes,  compare the nodes in stack with those in the second half
	// time O(N)   space O(N)
	private static boolean isPalindromeStack(LLNode root){
		if(root == null )
		     return true;
		LLNode slower = root;
		LLNode faster = root.next;
		Stack<String> stack = new Stack<String>();
		while(faster != null && faster.next != null ){
			stack.push(slower.data);
			slower = slower.next;
			faster =faster.next.next;
		}
		if(faster != null && faster.next == null){
			stack.push(slower.data);
		}
		slower = slower.next;
		while(slower!=null){
			String s = stack.pop();
			if(!s.equals(slower.data))
			     return false;
			slower=slower.next;
		}
		return true;
	}
	
	// recursive method
	private static WrappedR isPalindromeRecursive(LLNode root, int length){
		if(root == null || length == 0){
			return new WrappedR(null, true);
		}
		if(length == 1){
			return new WrappedR(root.next, true);
		}
		if(length == 2){
			return new WrappedR(root.next.next, true);
		}
		WrappedR ret = isPalindromeRecursive(root.next, length-2);
		
		if(ret.node == null || !ret.isPalindrome ){
			return ret;
		}
		else return new WrappedR(ret.node.next, ret.node.data.equals(root.data) );
	}
	
	
	// if modification is allowed, reverse the second half  in palce
	// compared the reversed list with the first half
	// time  O(N)   space O(1)
	private static boolean isPalindromeReverse(LLNode root){
		if(root == null )
		return true;
		LLNode slower = root;
		LLNode faster = root;
		while(faster != null && faster.next!=null){
			faster = faster.next.next;
			slower = slower.next;
		}		
		faster = slower.next;
		LLNode cursor = faster;
		while(cursor.next!=null){
			slower.next = new LLNode(cursor.next.data,faster);
			faster = slower.next;
			cursor.next = cursor.next.next;				
		}
		slower = root;
		while(faster!=null && slower!= null){
			if(!slower.data.equals(faster.data))
			      return false;
			slower = slower.next;
			faster = faster.next;
		}
		return true;
		
	}
}

class LLNode{
	String data;
	LLNode next;
	
	LLNode(String x, LLNode y){
		data = x;
		next = y;
	}
}
class WrappedR{
	LLNode node;
	boolean isPalindrome;
	
	WrappedR(LLNode x, boolean y){
		node = x;
		isPalindrome = y;
	}
}