234. Palindrome Linked List

How to solve Palindrome Linked List (LeetCode 234): the approach in brief

The problem

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Pattern

Palindrome Linked List is a Linked List Manipulation Patterns problem, in the In-place Reversal subpattern. The pattern covers in-place reversal, merging sorted lists, reordering, and intersection detection

Master in-place linked list reversal including full reversal, partial reversal, and k-group reversal techniques.

Approach outline

1. Consider how you might verify a palindrome property by comparing elements from both ends of the list.
2. Think about how to find the midpoint of the linked list efficiently, possibly using two pointers moving at different speeds.
3. Once you find the midpoint, consider reversing the second half of the list to facilitate comparison without extra space.

Complexity

The reference solution runs in O(n) time and O(1) space.

Asked at

Palindrome Linked List has been reported in interviews at Microsoft, Facebook, Amazon, Adobe, Capital One, Google, Oracle, Bloomberg.