Palindrome Linked List

LeetCode 234 • Easy • Linked Lists

Input: head = [1, 2, 2, 1] → Output: true
Find middle (fast/slow), reverse second half, compare first half with reversed second half.

TimeO(n)find mid + reverse + compare

SpaceO(1)pointers only

First: — Second: —

First half

Second (reversed)

Comparing

First

—

Second

—

Speed:

Ready

Press Play. 1) Find middle (fast/slow). 2) Reverse second half. 3) Compare first half with reversed second.

✎ Whiteboard

Size:3

⌨ Type It — Iterative

Practice until you don't need to look. The green highlights are the nuances to burn into memory.

═══ PALINDROME LINKED LIST — ITERATIVE ═══

PATTERN ▸ Find middle + reverse second half + compare O(n) · O(1)

① FIND MIDDLE

slow, fast = head, head

while fast and fast.next: slow, fast = slow.next, fast.next.next

② REVERSE SECOND HALF

prev=None, cur=slow; reverse

③ COMPARE

while second: if first.val!=second.val: return False

first, second = first.next, second.next

return True

▼ your implementation ▼

Verify your solution:

⌨ Type It — Recursive

Practice until you don't need to look. Recurse to end, compare with front pointer moving forward.

═══ PALINDROME LINKED LIST — RECURSIVE ═══

PATTERN ▸ Recurse to end, compare with front pointer O(n) · O(n)

① FRONT REF

front = head

② CHECK(node)

recurse to end; compare node.val with front.val

front = front.next

③ RETURN

return True if all match

▼ your implementation ▼

Verify your solution: