How can you check if a singly linked list is a palindrome without using extra data structures?

• A. Find the middle, reverse the second half in place, compare halves, then optionally restore.
• B. Push the first half values onto a stack and compare.
• C. Convert the list to a string and compare.
• D. Always return true if the list length is even.

Answer: (A)

Checking whether a singly linked list is a palindrome without extra data structures relies on mirroring the list around its center and comparing corresponding nodes in place. The standard approach uses two pointers to find the middle: move one pointer twice as fast as another, so when the fast pointer reaches the end, the slow pointer sits at the middle. Then reverse the second half of the list in place. With the second half reversed, walk from the list’s start and from the head of the reversed second half, comparing node values at each step. If all corresponding pairs match, the list reads the same forward and backward, so it’s a palindrome. For odd-length lists, you skip the single middle node during comparison because it has no counterpart. If you need to keep the original list intact, reverse the second half again to restore it. This method uses O(n) time and O(1) extra space, since all operations happen with pointer manipulation in place.

Using a stack would require extra space proportional to the list length, which is not allowed here. Converting the list to a string also uses extra memory and isn’t in-place. And a list being even in length does not guarantee palindrome status; palindrome depends on matching values, not just the length.