Check Whether a Singly Linked List Is a Palindrome
Company: Omnissa
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Check Whether a Singly Linked List Is a Palindrome
Given the values of a singly linked list in head-to-tail order, construct the linked list and determine whether its values form a palindrome.
Implement:
```text
isLinkedListPalindrome(values) -> boolean
```
Use a singly linked `Node` structure with `value` and `next` fields. The palindrome check must run in `O(n)` time and use `O(1)` auxiliary space after the list has been constructed. You may reverse part of the list in place. The empty list is considered a palindrome.
## Constraints
- `0 <= values.length <= 1,000,000`
- `-10^9 <= values[i] <= 10^9`
## Examples
### Example 1
```text
values = [1, 2, 3, 2, 1]
output = true
```
### Example 2
```text
values = [1, 2, 2, 3]
output = false
```
Overview: Construct a singly linked list and test whether its values form a palindrome. The exercise requires linear time and constant auxiliary space for the check, encouraging midpoint discovery, partial reversal, careful odd-length handling, and value comparison.
Read the full Omnissa Software Engineer interview experience this question came from
Given values in head-to-tail order, construct a singly linked list whose Node objects have value and next fields, then return whether its values form a palindrome. The palindrome check must run in O(n) time with O(1) auxiliary space after construction; reversing part of the list in place is allowed. The empty list is a palindrome.
Constraints
- 0 <= values.length <= 1,000,000
- -10^9 <= values[i] <= 10^9
- The empty list is a palindrome.
- After list construction, the check must use O(1) auxiliary space.
Examples
Input: ([1, 2, 3, 2, 1],)
Expected Output: True
Explanation: The values read the same from head to tail and tail to head.
Input: ([1, 2, 2, 3],)
Expected Output: False
Explanation: The first and last values already differ.
Hints
- Use fast and slow pointers to find the midpoint without storing node values separately.
- Reverse the first half while advancing the midpoint pointers, then compare the two halves.