Checking if Palindrome

Question: Define a method that checks if a given singly Linked List is a palindrome.

Related Tags:

1) Reverse and Comparing

You check to see that the first half of the reverse Linked List is the same as the first half of the original.

public boolean isPalindromeReversing() {

	// Strategy is to copy each element, then reverse it.
	CheckPalindrome<E> copyTestLinkedList = new CheckPalindrome<>();
	Node<E> n = this.head;

	// Copy each element O(n)
	while (n != null) {
		copyTestLinkedList.addToTail(n.getData());
		n = n.getNext();
	}

	// Reverse the LinkedList
	copyTestLinkedList.reverseIterative();

	// Now we have to compare our original to the reversed linked list
	Node<E> compareNode = copyTestLinkedList.head;

	// When our fast runner reaches the end, slow runner will be in the middle
	Node<E> slowRunner = this.head;
	Node<E> fastRunner = this.head;

	// Corner case when we only have two elements
	if (fastRunner.getNext().getNext() == null) {
		if (slowRunner.getData() != fastRunner.getNext().getData())
			return false;
		else
			return true;
	}

	// Check to see if it matches. Only have to up to half. O(n/2)
	while (fastRunner.getNext() != null 
		&& fastRunner.getNext().getNext() != null) {

		fastRunner = fastRunner.getNext().getNext();

		// If we find a node that doesn't match up, not a palindrome.
		if (slowRunner.getData() != compareNode.getData())
			return false;

		slowRunner = slowRunner.getNext();
		compareNode = compareNode.getNext();

	}

	return true;

}

Complexity

Time: O(n) Space: O(1)

2) Using a stack

Using a stack, push each element until you hit the middle. Then pop each element to see which ones match.

To figure out when you reach the middle, use slow and fast runners. The slow runner will move one node at a time, while the fast will run two nodes at a time. Thus, the slow runner will be in the middle when the fast runner reaches the end.

Complexity

Time: O(n) Space: O(n)

public boolean isPalindromeWithStack() {

	Node<E> slowRunner = this.head;
	Node<E> fastRunner = slowRunner;

	// Corner case when we only have two elements
	if (fastRunner.getNext().getNext() == null) {
		if (slowRunner.getData() != fastRunner.getNext().getData())
			return false;
		else
			return true;
	}

	// Use a stack to store each variable up to half way
	Stack<E> stack = new Stack<>();

	stack.push(slowRunner.getData());

	while (fastRunner != null 
		&& fastRunner.getNext() != null) {

		fastRunner = fastRunner.getNext().getNext();
		slowRunner = slowRunner.getNext();

		stack.push(slowRunner.getData());
	
	}

	// If number of elements is odd, then advance
	if (fastRunner.getNext() != null) {
		slowRunner = slowRunner.getNext();
	}

	while (slowRunner != null) {

		if (slowRunner.getData() != stack.pop())
			return false;

		slowRunner = slowRunner.getNext();

	}

	return true;

}

3) Recursively

We can solve recursively as well. We send two references to our function isPalindromeRecursion function, left and right. Once the right has gone to the tail of our linked list, we return the left reference.

The algorithm then determines if the left matches with our right. If so, it returns the next element relative to the current left. If it doesn't match, it returns null, meaning, it is not a palindrome.

Complexity

Time: O(n) Space: O(n)

public Node<E> isPalindromeRecursion(Node<E> left, Node<E> right) {

	// If reached end, return the front
	if (right == null) {
		return left;
	}

	left = isPalindromeRecursion(left, right.getNext());

	if (left != null) {

		if (left.getData() == right.getData())
			if (left.getNext() != null) 
				return left.getNext();
			else
				return left;
	}

	// if left is null then not a palindrome
	return null;

}

Came up with a better solution or have a question? Comment below!

Next Challenge: Reverse a String