Palindrome Linked List

Explanation & Solution

Description

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

You must solve it in O(n) time and O(1) space.

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

Output: true

Explanation: The values read the same forwards and backwards: 1 → 2 → 2 → 1.

Fast and Slow Pointers pattern

If the list is empty or has only one node, it is trivially a palindrome — return true.

Use two pointers: slow moves one step at a time, fast moves two steps.
When fast reaches the end, slow is at the middle (or just before the second half for even-length lists).

Starting from slow.next, reverse the linked list in-place.
Use three variables: prev, curr, and next to reverse the pointers one by one.
After reversal, prev points to the head of the reversed second half.

Walk two pointers: left from the head and right from the head of the reversed second half.
At each step, compare left.val and right.val.
If any pair differs, the list is not a palindrome — return false.
If all pairs match, return true.

By reversing only the second half, we can compare the list from both ends without using extra space.

Time

O(n)finding the middle is O(n), reversing is O(n), comparing is O(n).

Space

O(1)only a constant number of pointer variables are used.

Input:

Linked List Traversal

—

Press play to start traversal

Slow (S)Fast (F)Both

7 steps