Palindrome Linked List
Check if a linked list is a palindrome.
Problem Understanding
Given the head of a singly linked list, return true if it is a palindrome. A palindrome reads the same forwards and backwards.
Example: 1 -> 2 -> 2 -> 1 is true. 1 -> 2 is false.
Attempt 1: Copy to Array (Brute Force)
The simplest way is to copy all node values into an array (or ArrayList) and then check if the array is a palindrome using two pointers. This is easy to implement but requires O(N) extra space.
Visualizing the Issue
Can we do this in O(1) space? We can't traverse backwards in a singly linked list. However, if we could reverse the second half of the list, we could compare it with the first half!
The Intuition: Middle & Reverse
- Find the Middle of the list (using Tortoise and Hare).
- Reverse the second half of the list in-place.
- Compare the start of the list with the start of the reversed half.
- (Optional) Restore the list by reversing again.
Interactive Walkthrough
Initializing...
Observe finding the middle, visualizing the reverse (conceptually), and comparing pointers.
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.