Katkat
Back

Check a Linked List Palindrome Without Mutating It

MicrosoftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.

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?

Hints

Hint 1

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 2

Restoration is part of correctness: Keep enough information to reverse the modified half again and reconnect it before returning, including on a mismatch.