I’ve been working a lot with the Linked List lately, and I thought I’d try a more practical problem today.

### Problem

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

As a follow up, the question also mentions:

Could you do it in O(n) time and O(1) space?

### Solution

Funnily enough, despite being marked as an ‘Easy’ problem, the acceptance rate on this question is quite low, *30.5%*.

So let’s break down the approach. We are using a singly linked list, and are not given the size of the Linked List. The only fields are the value, and the next node. The starting code provided by the question is below:

I’ll use this basic approach:

- Get the half-way point of the list.
- Reverse the second half of the list.
- Compare the two halves.

I can reverse the list by using two pointers, one of which will move 2 nodes at a time, while the other moves 1. If we check when the faster ptr reaches the end, then the slower ptr will be at the half.

Step one is done, now time to reverse the second half of the list. This is a singly linked list, so we will need to use three pointers to achieve this.

**prev** will point to the previous node. **curr** will point to the current node. **nextBuffer** will point to the next node.

- We will
*store*the next node in nextBuffer. - Because we are reversing, we will then
*set*the next value in**curr**to the value of**prev**, which will initially be null. - We will then set
**prev**to**curr**, when we increment curr, then**prev**will accurately represent the previous node. - Finally, we increment
**curr**by setting it the value of the**nextBuffer**which we set in step 1.

Step two done! Now it’s just a matter of comparing the two halves. The **head** pointer represents the first half of the list, while the **prev** pointer contains the second, reversed, half of the list.

The final (submitted) solution is below:

All the test cases passed, but only beating 34.92% of other Java submissions isn’t anything to brag about…. 2ms is quite slow.

The alternatives to my solution are a stack-based solution, and a recursive solution. All of these have O(n) time complexity, but could very well be much quicker.

Thanks for reading.