Check if a Linked List Is a Palindrome

Given the head of a singly linked list, determine whether it reads the same forwards and backwards. The optimal solution can't just compare from both ends the way an array would, since a singly linked list has no backward pointer to walk in reverse. Instead it finds the middle with slow and fast pointers, reverses everything from the middle onward, and then walks two pointers outward — one across the untouched front half, one across the newly-reversed back half — checking that every pair of values matches. If they all match, it's a palindrome.

Test Case 1:

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

Output:true

Explanation:Reads the same forwards and backwards.

Test Case 2:

Input:head = [1, 2]

Output:false

Explanation:1, 2 reversed is 2, 1 — not the same.

Test Case 3:

Input:head = [1]

Output:true

Explanation:A single node is trivially a palindrome.

Constraints

◆1 ≤ number of nodes in head ≤ 500
◆-100 ≤ node value ≤ 100

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

head (list values) — 1-8 integers

1	class Solution {
2	public boolean isPalindrome(Node head) {
3	if (head == null \|\| head.next == null) {
4	return true;
5	}
6	Node slow = head, fast = head;
7	while (fast != null && fast.next != null) {
8	slow = slow.next;
9	fast = fast.next.next;
10	}
11	Node prev = null;
12	Node curr = slow;
13	while (curr != null) {
14	Node nextNode = curr.next;
15	curr.next = prev;
16	prev = curr;
17	curr = nextNode;
18	}
19	Node p1 = head, p2 = prev;
20	while (p2 != null) {
21	if (p1.val != p2.val) {
22	return false;
23	}
24	p1 = p1.next;
25	p2 = p2.next;
26	}
27	return true;
28	}
29	}
30

1

2

1

null

Variables

head1

COMPARE

More than one node — the real check has to run.

Step 1 / 32

Approach & Solutions

Brute Force — Copy to an Array, Two-Pointer Check

Good

Copy every node's value into an array, then check whether that array reads the same forwards and backwards using two pointers closing in from both ends. Correct and simple, but it costs an array the size of the whole list — the optimal solution gets the same answer without allocating anything proportional to n.

TimeO(n)

SpaceO(n)

Java

Try it out

// Node definition used in this problem:
// class Node {
//     int val;
//     Node next;
// }

class Solution {
    public boolean isPalindrome(Node head) {
        List<Integer> vals = new ArrayList<>();
        Node curr = head;
        while (curr != null) {
            vals.add(curr.val);
            curr = curr.next;
        }
        int lo = 0, hi = vals.size() - 1;
        while (lo < hi) {
            if (!vals.get(lo).equals(vals.get(hi))) {
                return false;
            }
            lo++;
            hi--;
        }
        return true;
    }
}

Optimal — Find the Middle, Reverse the Second Half, Compare

Optimal

Find the middle with slow/fast pointers, reverse the second half in place (the exact same relink primitive used to reverse any run of nodes), then walk two pointers outward from the middle — one over the untouched front half, one over the freshly-reversed second half — comparing values as they go. If every pair matches, it's a palindrome. The list ends up with its second half reversed, but that's a fine trade for doing the whole check in O(1) extra space.