Reference: LeetCode

Difficulty: EasyTwo Pointers

My Post: Java Solution Using Two Pointers, Half Reverse (easy-understand)

## Problem

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

**Example:**

1 | Input: 1->2 |

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

1 | public boolean isPalindrome(ListNode head) { |

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

1 | // even |

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.

1 | private ListNode getRightHalf(ListNode head) { |

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

.

1 | // left-leaning |

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:

1 | public boolean isPalindrome(ListNode head) { |

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

1 | Example: 1 -> 2 -> 3 -> 4 -> 5 |

The remaining helper function `reverse()`

:

1 | // iteration |

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