Check a Linked List Palindrome Without Mutating It
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement `linked_list_palindrome(values)`, where `values` is the traversal-order serialization of a singly linked list of integer values.
Return whether the values read the same from front to back and back to front. The console uses an array serialization for portable input and output, but the required linked-list algorithm uses `O(n)` time and `O(1)` auxiliary pointer space. Most importantly, it must restore every `next` pointer before returning so a caller observes exactly the original list structure.
An empty list and a one-node list are palindromes.
```hint Reuse the second half
Find the midpoint with slow and fast pointers, reverse the second half in place, and compare it with the first half.
```
```hint Restoration is part of correctness
Keep enough information to reverse the modified half again and reconnect it before returning, including on a mismatch.
```
### Discussion Extensions
- How does the midpoint handling differ for odd- and even-length lists?
- What bug appears if the function returns immediately on the first mismatch?
Overview: Check whether a singly linked list is a palindrome in O(n) time and O(1) pointer space without leaving it modified. Practice finding the midpoint, reversing the second half, comparing values, and restoring every link before return.
Read the full Microsoft Software Engineer interview experience this question came from
Implement linked_list_palindrome(values), where values serializes a singly linked list in traversal order. Return whether the list is a palindrome using linear time and constant auxiliary pointer space, and restore every next pointer before returning.
Constraints
- 0 <= values.length <= 100.
- Each node value is an integer from -1,000,000,000 through 1,000,000,000.
- The implementation must restore the exact original linked-list structure before returning.
Examples
Input: [1, 2, 1]
Expected Output: True
Input: [1, 2]
Expected Output: False
Hints
- Find the midpoint with slow and fast pointers, then reverse only the second half.
- Save the reversed-half head and reverse that half again after comparison, even when a mismatch is found.