# 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.

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

// Now we have to compare our original to the reversed linked list

// When our fast runner reaches the end, slow runner will be in the middle

// 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> 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: