DSA problem

Palindrome Linked List

EasyLinkedList In-place ReversalPattern: LinkedList In-place Reversaltop300AmazonMicrosoftMetaAppleBloombergGoogle

Given the head of a singly linked list, return true if the list reads the same forwards and backwards, and false otherwise. A list is a palindrome when the sequence of node values is identical to its reverse.

The naive solution copies every value into an array and then compares the array with its reverse using two indices. That works in O(n) time but uses O(n) extra space — wasteful for a problem that has a much cleaner in-place answer.

The optimal approach blends three classic linked list techniques. First, use the fast and slow pointer idiom to locate the middle of the list in one pass: when fast reaches the end, slow sits at the middle. Second, reverse the second half of the list in place using the iterative three-pointer reversal pattern. Third, walk a pointer from the original head and another from the new head of the reversed second half, comparing values one by one until either half is exhausted.

If every compared pair matches, the list is a palindrome. Because the second half is shorter or equal in length to the first half, you can safely stop the comparison when the reversed half runs out. This entire procedure runs in O(n) time and uses only O(1) extra space, since no auxiliary array is ever allocated. (Restoring the original list by reversing the second half again is optional but considered good hygiene.)

Examples

Example 1

Input: head = [1,2,2,1]

Output: true

Explanation: The middle splits the list into [1,2] and [2,1]. Reversing the second half gives [1,2], which matches the first half value by value, so the list is a palindrome.

Example 2

Input: head = [1,2]

Output: false

Explanation: The two halves are [1] and [2]. After reversing the second half it is still [2], and 1 differs from 2, so the list is not a palindrome.

Example 3

Input: head = [1,2,3,2,1]

Output: true

Explanation: With odd length 5, slow lands on the middle node (value 3). Reversing the tail [3,2,1] yields [1,2,3], which matches the first three values 1, 2, 3.

Constraints

The number of nodes in the list is in the range [1, 10^5].
0 <= Node.val <= 9
Follow up: Could you do it in O(n) time and O(1) space?

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

linked-listtwo-pointersin-place-reversalfast-slow-pointers

Browse all DSA problems