Check a Linked List Palindrome Without Mutating It

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?

Check a Linked List Palindrome Without Mutating It

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

Example 1

Input: [1, 2, 1]
Output: True

Example 2

Input: [1, 2]
Output: False

Hints

1. Find the midpoint with slow and fast pointers, then reverse only the second half.
2. Save the reversed-half head and reverse that half again after comparison, even when a mismatch is found.

Approach

Build the portable list serialization, locate the midpoint, reverse the second half in place, and compare it against the first half. Record a boolean instead of returning early, then reverse and reconnect the second half so restoration is part of correctness.

• Time complexity: O(n)
• Space complexity: O(1) auxiliary pointer space after constructing the serialized input list