234. Palindrome Linked List

Quick Identifier

Topic: linked-list
Pattern: In-place Linked List Reversal + Fast & Slow
Difficulty: Easy
Companies: Amazon, Google, Meta, Apple, Microsoft
Frequency: Very High
LeetCode: 234

Quick Sights

Time Complexity: O(n) from the optimal approach.
Space Complexity: O(1) from the optimal approach.
Core Mechanism: Return true if a singly linked list reads the same forward and backward. Aim for O(n) time and O(1) extra space (so no full array copy of values).

Concept Explanation

Return true if a singly linked list reads the same forward and backward. Aim for O(n) time and O(1) extra space (so no full array copy of values).

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

Palindrome on a list
Space O(1) follow-up
Find middle with slow/fast, reverse second half, compare, optionally restore (not always required in judge)

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — O(n) time / O(n) space — copy values to slice and two-pointer ends.
Better — recursion stack — O(n) implicit space.
Optimal — O(n) time / O(1) space — split via slow/fast, reverse second half (skip middle on odd length), compare node-wise.

Optimal Solution

Go

type ListNode struct {
	Val  int
	Next *ListNode
}

func isPalindrome(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	if fast != nil {
		slow = slow.Next
	}
	second := reverseList(slow)
	first := head
	for second != nil {
		if first.Val != second.Val {
			return false
		}
		first = first.Next
		second = second.Next
	}
	return true
}

func reverseList(head *ListNode) *ListNode {
	var previous *ListNode
	current := head
	for current != nil {
		next := current.Next
		current.Next = previous
		previous = current
		current = next
	}
	return previous
}

JavaScript

class ListNode {
	constructor(val = 0, next = null) {
		this.val = val;
		this.next = next;
	}
}

function isPalindrome(head) {
	if (head === null || head.next === null) {
		return true;
	}
	let slow = head;
	let fast = head;
	while (fast !== null && fast.next !== null) {
		slow = slow.next;
		fast = fast.next.next;
	}
	if (fast !== null) {
		slow = slow.next;
	}
	let second = reverseList(slow);
	let first = head;
	while (second !== null) {
		if (first.val !== second.val) {
			return false;
		}
		first = first.next;
		second = second.next;
	}
	return true;
}

function reverseList(head) {
	let previous = null;
	let current = head;
	while (current !== null) {
		const next = current.next;
		current.next = previous;
		previous = current;
		current = next;
	}
	return previous;
}

Walkthrough

[1,2,2,1] — slow stops at second 2; even length so no skip; reverse second half 2->1 to 1->2; walk together 1==1, 2==2.

Invariant: after reversal, second half length matches first half length for palindrome checks.

Edge Cases

Empty or single node — trivially palindrome.
Two nodes only — compare once after reversal path.

Pitfalls

Odd length lists — advance slow once when fast not nil so middle node is excluded from comparison.
Mutating list for online systems — restore links if required by API contract.

Variants

Restore list after check — reverse second half again and reconnect.
Compare digits as strings — same flow with char nodes.

Mind-Map Tags

#linked-list #palindrome #middle-split #reverse-half