CareerCup_2.7 - Check List Palindrome

CheckPalindrome.java

package Chapter2;

public class CheckPalindrome {
    
    //return type for recursion, contains both symmetric nodes
    //for the target node in list and the recursive result
    private static class Pair<T> {
	private boolean result;
	private Node<T> node;

	private Pair(boolean res, Node<T> n) {
	    result = res;
	    node = n;
	}
    }

    public static <T> boolean isPalindrome(MyLinkedList<T> list) {
	if (list == null || list.head == null)
	    return false;
	int n = len(list);
	Pair<T> pair = check(list.head, n % 2 == 0 ? n / 2 - 1 : n / 2, n % 2 == 0);
	return pair.result;
    }

    private static <T> Pair<T> check(Node<T> node, int remain,
	    boolean evenNodesInTotal) {
	// base case, middle point of the list
	if (remain == 0) {
	    return evenNodesInTotal ? new Pair<>(node.data == node.next.data,
		    node.next) : new Pair<>(true, node);
	}

	// call recursively check the next node with its symmetric nodes in list
	Pair<T> p = check(node.next, remain - 1, evenNodesInTotal);
	return new Pair<>(p.result && node.data == p.node.next.data,
		p.node.next);
    }

    //get length of list
    private static <T> int len(MyLinkedList<T> list) {
	int l = 0;
	Node<T> cur = list.head;
	while (cur != null) {
	    cur = cur.next;
	    l++;
	}
	return l;
    }

    public static void main(String args[]) {
	String s = "minim";
	MyLinkedList<Character> list = new MyLinkedList<>(new Character[] {
		'm', 'i', 'n', 'i', 'm' });
	System.out.println("isPalindrome(" + s + ") = " + isPalindrome(list));
    }
}

MyLinkedList.java

package Chapter2;

//Singly Linked List
public class MyLinkedList<T> {
    public Node<T> head;

    public MyLinkedList(Node<T> h) {
	head = h;
    }

    public MyLinkedList() {
	head = null;
    }

    public MyLinkedList(T[] dataArray) {
	if (dataArray == null || dataArray.length <= 0)
	    return;
	head = new Node<>(dataArray[0], null);
	Node<T> node = head;
	for (int i = 1; i < dataArray.length; i++) {
	    node.next = new Node<T>(dataArray[i], null);
	    node = node.next;
	}
    }
}

Node.java

package Chapter2;

public class Node<T> {
    public T data;
    public Node<T> next;
    
    public Node(T d, Node<T> n){
	data = d;
	next = n;
    }
}