Skip to main content

234. Palindrome Linked List

easy

Determine whether a singly linked list reads the same forward and backward. The follow-up — do it in O(n) time and O(1) space — forces a clever combine of cycle-detection and reversal techniques.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Constraints

  • The number of nodes in the list is in the range [1, 10^5].
  • 0 <= Node.val <= 9

Examples

Example 1

Input
head = [1,2,2,1]
Output
true

Example 2

Input
head = [1,2]
Output
false

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Copying values into an array and using two pointers is O(n) time AND O(n) space — works but doesn't satisfy the O(1)-space follow-up.

Hint 2

For O(1) space: find the middle (Floyd's), reverse the second half, then compare both halves.

Hint 3

Restore the list before returning if the interviewer cares about mutation.

Solution approach

Reveal approach

Three-step O(1)-space approach. (1) Find the middle with slow/fast pointers — slow advances one step, fast two; when fast hits the end, slow is at the midpoint. (2) Reverse the linked list starting at slow.next (or slow for odd-length lists). (3) Walk the first half and the reversed second half in parallel and compare values. Any mismatch returns false. If the reversed-half pointer reaches null, return true. Optionally restore the list by reversing the second half back. O(n) time, O(1) extra space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • linked-list
  • two-pointers
  • reversal

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Palindrome Linked List and Linked Lists problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →