check a single node list is Palindrome, use fast and slow runner to find the middle element and store the second half list to compare with the first half of the original list

isPalindrome.java

	/**
	 * This solution does not to store the whole link of nodes
	 * only the first half is needed to be stored so it is friendly 
	 * for space complexity. It use fast runner and slow runner to 
	 * find the middle point of the list of node.
	 * @param list
	 * @return
	 */
	
	// Note: When I implemented this method I made two mistakes:
	// 1. find the beginning point of the latter half of the link
	//    no matter whether fast runner has next node(equals whether
	//    odd or even number of elements the node list have)
	//    That is to say the right point is the next node of the 
	// 	  slow runner when fast runner stops
	// 2. the condition of the fast runner stops, warning! it is not 
	// 	  simply while (fast.next.next != null) because if fast.next 
	// 	  is null then access of fast.next.next will throw the nullException
	// 	  <em>So the right way is to use the short circuit therome like:
	//    while (fast.next != null && fast.next.next != null) <em>
	// 	  the loop stops when fast.next is null.
	
	public static boolean isPalindrome_v2(Node list) {
		
		Node fast = list;
		Node slow  = list;
		
		Stack<Integer> halfReverse = new Stack<Integer>();
		if (list.next  == null) {
			return false;
		} else if (list.next.next == null) {
			return list.val == list.next.val;
		}
		
		while (fast.next != null && fast.next.next != null) {
			slow  = list.next;
			fast = fast.next.next;
		}
		
		slow  = slow.next;   // this is the beginning element to store in the stack as the second half the link list.
		while (slow != null) {
			halfReverse.push(slow.val);
			slow = slow.next;
		}
	
		while (!halfReverse.isEmpty()) {
			if (list.val != halfReverse.pop()) {
				return false;
			}
			list = list.next;
		}
		
		return true;
	}