Palindrome Linked List - Video Solutions

Problem Overview: You are given the head of a singly linked list. The goal is to determine whether the sequence of node values reads the same forward and backward. In other words, check if the linked list forms a palindrome without modifying the logical order of elements.

Approach 1: Convert to Array and Use Two Pointers (O(n) time, O(n) space)

This approach copies the linked list values into a dynamic array or vector while iterating through the list once. After that, apply the classic two pointers technique: one pointer starts at the beginning of the array and the other at the end. Compare elements while moving inward. If every pair matches, the sequence is a palindrome.

The key insight is that arrays allow constant-time index access, which makes comparing mirrored elements trivial. This solution is straightforward to implement and easy to reason about, especially for beginners. The tradeoff is additional memory because the entire list is stored in an array.

Approach 2: Reverse Second Half and Compare (O(n) time, O(1) space)

This is the optimal in-place technique commonly expected in interviews. First locate the midpoint of the list using the fast and slow pointer technique from two pointers. When the fast pointer reaches the end, the slow pointer sits at the middle. Reverse the second half of the list starting from that midpoint.

Once reversed, compare nodes from the beginning of the list with nodes from the reversed half. If every value matches, the linked list is a palindrome. Reversal works because the second half now appears in reverse order, allowing direct pairwise comparison.

The advantage is constant extra memory since operations happen directly on the linked list. The only additional work is reversing half the list and optionally restoring it afterward. The algorithm performs a single pass to find the midpoint, another pass to reverse, and a final comparison pass, which still results in linear time.

Recommended for interviews: Start by explaining the array approach to demonstrate the core palindrome idea. Then optimize to the in-place method by reversing the second half. Interviewers typically expect the O(n) time and O(1) space solution because it shows comfort with linked list manipulation and pointer techniques.