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 Sam K., 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

More Linked Lists practice problems

See all Linked Lists problems →