How do you check a linked list palindrome in O(1) space?

Find the middle with slow and fast pointers, reverse the list from the middle, then walk one pointer from head and one from the reversed half, comparing values until the reversed half ends.

Does this solution change the input list?

Yes. It leaves the second half reversed when it returns. If the list must stay intact, reverse the second half again before returning.

How are odd-length lists handled?

For an odd length, slow stops on the middle node and it is included in the reversed half, so it is compared with itself on the last comparison.

Palindrome Linked List

Check if a linked list is a palindrome.

EasySolve on LeetCode

Problem Understanding

Starting from head, decide whether the values of a singly linked list read the same from front to back as from back to front.

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.
This solution stops there and does not restore the list: when it returns, the second half is still reversed. Reverse it again before returning if the caller needs the list intact.

Interactive Walkthrough

[1, 2, 2, 1]

START AT HEAD

head slow fast

→

→ NULL

Phase

middle

Answer

—

slow and fast start at head, node 0 (1)

slow moves one node to node 1 (2); fast moves two to node 2 (2)

Values

Legend & Complexity

The node a pointer is on: slow, then left

fast, then right

Reversed: its next now points back toward the middle

A pair that does not match

→ n: a link into the other row

Time

O(n)

Space

O(1)

Watch slow and fast find the middle, then each link in the second half flip to point back toward the middle — the reversed half becomes its own row, ending where it joins the first half. left and right then compare values pair by pair. The last step shows the list as the code leaves it: second half still reversed.

Dry Run Table

Input: 1 -> 2 -> 3 -> 2 -> 1 (nodes #0 to #4)

Step	Action	State
1	Find the middle	`slow` moves `#0 → #1 → #2`; `fast` moves `#0 → #2 → #4`, whose `next` is `NULL`. `slow` stops at `#2` (value `3`).
2	Reverse from `slow`	`#2 → NULL`, `#3 → #2`, `#4 → #3`. The reversed half reads `1 -> 2 -> 3`; `#1` still points at `#2`.
3	Compare	`left` `#0` (1) vs `right` `#4` (1): match
4	Compare	`left` `#1` (2) vs `right` `#3` (2): match
5	Compare	`left` `#2` (3) vs `right` `#2` (3): match, and `right` becomes `NULL`
6	Return	true — with the second half still reversed

The Solution Template

Fast/Slow Pointers + In-Place Reversal.

Palindrome Linked List Code

1var isPalindrome = function(head) {
2    let slow = head, fast = head;
3    while (fast && fast.next) {
4        slow = slow.next;
5        fast = fast.next.next;
6    }
7    let prev = null;
8    while (slow) {
9        let temp = slow.next;
10        slow.next = prev;
11        prev = slow;
12        slow = temp;
13    }
14    let left = head, right = prev;
15    while (right) {
16        if (left.val !== right.val) return false;
17        left = left.next;
18        right = right.next;
19    }
20    return true;
21};

Edge Cases & Common Mistakes

Single Node: Always a palindrome.
Two Nodes: Check equality.
Original List Modified: This solution does not restore the list — after it returns, the second half is still reversed. In an interview, ask whether the input must be left intact; if so, reverse the second half again before returning.

Summary

Combining 'Fast/Slow Pointers' with 'Reverse Linked List' allows us to solve this problem efficiently in both time and space.

Linked List Cycle

Remove Nth Node From End of List