Linked List · 110Easy
Palindrome Linked List
Given the head of a singly linked list, return true if it reads the same forwards and backwards. Aim for O(n) time and O(1) space.
Constraints
- The list holds 1 to 10^5 nodes.
- 0 <= Node.val <= 9
- INPUT FORMAT
- `head` is a ListNode object, not an array. The arrays in EXAMPLES list the node values in
- order; the test runner links them into real nodes before calling your function.
Examples
isPalindrome(1 -> 2 -> 2 -> 1) -> true isPalindrome(1 -> 2) -> false isPalindrome(1) -> true isPalindrome(1 -> 2 -> 1) -> true // odd length, middle node skipped isPalindrome(0 -> 0) -> true // two equal nodes isPalindrome(1 -> 0 -> 1 -> 1) -> false // nearly symmetric, but not quite
Edge cases
- A single node is a palindrome.
- Odd lengths leave a middle node that can be skipped.
- FOLLOW-UP
- Copying values to an array is O(n) space and misses the target.
Show the target complexity (spoiler)
- Naive
- O(n) time, O(n) space — copy the values into an array and compare with two pointers.
- Target
- O(n) time, O(1) space — find the middle with slow/fast pointers, reverse the second half, compare the halves, then restore the list.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/06-linked-list/110-palindrome-linked-list.js ./practice c 110