Example 1
ready- Input
head = [ 1, 2, 2, 1 ]- Expected
true- Why
- the values mirror each other around the center
Palindrome Linked List
25 min · isPalindrome()A list can mirror itself even though its links only point forward. The trick is deciding how much memory you need to see that mirror.
A palindrome is a sequence that reads the same from left to right and right to left.
A singly linked list is a chain of nodes where each node links only to the next one.
Given the head of one such list, return true when its values form a palindrome;
otherwise, return false.
A few ground rules:
- Compare node values, not the identities of the nodes that hold them.
- Both odd-length and even-length lists can be palindromes.
- A one-node list always returns
true.
Constraints
1 <= list length <= 10_000-1_000_000_000 <= Node.val <= 1_000_000_000
Hints
Start with an array
Copy every node value into an array. Arrays let you compare the first value with the last, the second with the second-last, and so on.
Find the halfway point
To avoid the array, move one pointer one node at a time and another two nodes at a time. When the faster pointer finishes, the slower one is at the second half.
Make both halves face you
Reverse the second half in place. Now one pointer can walk from the original head while another walks from the reversed tail, comparing matching values.
Follow-up
Can you restore the second half after the comparison so callers receive the list in its original shape, while keeping O(n) time and O(1) extra space?
Visible cases
Examples
Example 2
ready- Input
head = [ 1, 2 ]- Expected
false- Why
- the first and last values differ
Example 3
ready- Input
head = [ 1 ]- Expected
true- Why
- a single value reads the same in both directions
Interview signal
Asked at
AmazonMetaMicrosoft
Collect + compare
Copy the values into an array, where backward access is easy, then compare that array with its reverse.
def is_palindrome(head: ListNode | None) -> bool:
values: list[int] = []
current = head
while current is not None:
values.append(current.val)
current = current.next
return values == values[::-1]This version is hard to get wrong. The cost is one extra array slot for every node.
Time O(n) — collect once and compare once. Space O(n) for the copied values and their reversed copy.
Reverse the second half
You can turn half of the list into the backward view you need:
- Move
slowone step andfasttwo steps untilfastreaches the end.slownow starts the second half (or sits on the middle node for an odd-length list). - Reverse the chain from
slowonward. - Walk from the original head and from the reversed half together. Any unequal pair
proves the answer is
false.
def is_palindrome(head: ListNode | None) -> bool:
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
previous = None
current = slow
while current is not None:
next_node = current.next
current.next = previous
previous = current
current = next_node
left = head
right = previous
while right is not None:
if left is None or left.val != right.val:
return False
left = left.next
right = right.next
return TrueFor an odd length, the reversed half includes the middle node. That's fine: the final comparison pairs that middle value with itself. For an even length, both halves have the same size.
Time O(n) — finding the middle, reversing, and comparing are all linear passes. Space O(1) — the algorithm moves a fixed number of node references.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
true
Run: visible + custom · Submit: full suite