234. Palindrome Linked List

At a Glance

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

Problem (one-liner)

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).

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)

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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.

Similar Problems

• 206. Reverse Linked List — reversal helper.
• 143. Reorder List — another middle-split workflow.
• 92. Reverse Linked List II — precise subrange reversal.

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