Leetcode: Given a singly linked list, determine if it is a palindrome.

Consider example a->b->b->a returns true.
a->b->b returns false.

This question can be solved with recursion.

source: https://leetcode.com/problems/palindrome-linked-list/

Use two pointers left and right. Move right and left using recursion and check for following in each recursive call.

• 1) Sub-list is palindrome.
• 2) Value at current left and right are matching.

If both above conditions are true then return true.

The idea is to traverse first to the end of the list and then start traversing back while making the comparison. This can be addressed either using a stack or using recursion call. Advantage of using recursion over stack is in optimizing the extra memory used by stack. Recursion is nothing but a stack where function calls are stored in memory as a stack.

In order to access first node of list, we need list head to be available in the last call of recursion. Hence we pass head also to the recursive function. If they both match, compare (2, n-2) nodes. This way, everytime a call to recursion is done, the left node will move to next, where as with recursion, head will move in backward direction.

The LinkedList for the example is singly. Here is how Node class looks like:

class ListNode {
	int value;
	protected ListNode next;
	
	public Node(int value) {
		this.value = value;
	}
	
	public int getValue() {
		return value;
	}
}

public class Palindrome {

	private ListNode left;
	public boolean isPalindrome(ListNode head) {
		left = head;
		return checkValue( head);
	}
	private boolean checkValue(ListNode right) {
		if(right == null)
			return true;
		boolean val = checkValue( right.next);
		if(!val)
			return false;
		boolean v = left.val == right.val;
		left =left.next;
		return v;
	}
}