Reference: LeetCode
Difficulty: EasyTwo Pointers

## Problem

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

Example:

Follow up: Could you do it in $O(n)$ time and $O(1)$ space?

## Analysis

### Reverse Whole

Reverse the whole list and compare each element, but reversal should be non-destructive because we need to do comparison later.

Note: Non-destructive reversing can be tricky at the first glance.

Time: $O(N)$
Space: $O(N)$

### Reverse Half

The idea is to reverse the right half of the original list and then compare half elements. The difficulties lie in:

• Handle even and odd cases.
• How to get the right half.

To get the right half, we have two ways: Traversal based on the length, Slow-fast pointers. Here we use the slow-fast pointers to find the middle point.

In the examples above, which nodes do we want as heads of the right half? 3 (even case) and 4 (odd case).

So we can find the left-leaning middle point 2 and the exact middle point 3 by slow-fast pointers. Finally, returns their the next node.

In terms of left-leaning and right-leaning, check out the code and examples to get an intuition.

In the code, the difference is in the initializations of fast.

By observation, we want to use left-leaning in this case because slow could finally stop at the left-leaning middle point.

Here is the code:

Note: We use p2 instead of p1 as our while-condition because p1 actually points to the list of all elements (reverse and getRightHalf do not disconnect the list). For example:

The remaining helper function reverse():

Time: $O(N)$
Space: $O(1)$ if not using recursion.

Comment Junhao Wang
Hi, I was a master student at USC studying Computer Science.