96. Check if a Linked List Is a Palindrome

A singly linked list has n node values. Print 'Yes' if the sequence of values reads the same forwards and backwards, otherwise print 'No'.

Input: The first line contains an integer n. The second line contains n space-separated integers, the linked list's values in order. Output: Print 'Yes' if the values form a palindrome, otherwise print 'No'.

1 <= n <= 10^5

A single-node list is trivially always a palindrome - a good sanity-check base case, and combining the 'find middle' and 'reverse a list' techniques (both already mastered from earlier problems) is what makes this one approachable rather than intimidating.

Check whether a linked list's values read the same forwards and backwards. Brute force: Copy every value into an array, then check if the array reads the same forwards and backwards using two pointers - this works but costs O(n) extra space for the array, when the list itself can be temporarily modified and restored to avoid it. Optimised: Finding the middle and reversing just the SECOND HALF in place (rather than copying values into a separate array) lets you compare the two halves directly using the list's own existing nodes, achieving O(1) extra space beyond a few pointers - the second half can optionally be reversed back afterward if the original list structure must be preserved.

Use recursion to reach the end of the list first (recursing on the 'rest' of the list before doing any comparison), implicitly using the call stack to remember each node in reverse order as the recursion unwinds. On the way back out of the recursion, compare each node (moving backward, from the tail toward the head) against a separate pointer that started at the head and advances forward one step per unwind. This achieves the same effect as an explicit reversed copy or stack, but without allocating a separate array or stack structure - the language's own call stack does that job instead. Time: O(n) Space: O(n) (call stack)

Traverse the linked list once, copying every value into an array. Then use two indices, one starting at the front and one at the back of the array, moving them toward each other and comparing values at each step; if all corresponding pairs match, the list is a palindrome. This is straightforward and correct because comparing the array from both ends is equivalent to comparing the list forwards and backwards, but it requires an auxiliary array holding every value. Time: O(n) Space: O(n)

Find the middle of the list using the slow/fast pointer technique (fast moves two steps for every one step of slow), then reverse the second half of the list in place by relinking next pointers as you go, with no extra array or recursion. Walk the first half and the now-reversed second half in tandem comparing values; if all match, it's a palindrome. Optionally reverse the second half back afterward to restore the original list. This is the only approach that needs no auxiliary storage proportional to n at all - just a constant number of pointers - making it the true optimum in space while remaining linear in time. Time: O(n) Space: O(1)

1. Find the MIDDLE of the list using the slow/fast pointer technique. 2. REVERSE the second half of the list (starting from the middle). 3. Compare the reversed second half against the first half, node by node - if every pair matches, it's a palindrome.

Time: O(n) - finding the middle, reversing the second half, and comparing are all linear passes. Space: O(1) extra space (beyond pointers), if the second half is reversed in place rather than copied.

n = 1, always a palindrome (per the hints); an even n, where both middle elements must match; n = 10^5 for performance.

Be ready to mention that if the ORIGINAL list structure must be preserved afterward (not just checked), the second half should be reversed BACK to its original order once the comparison is done - a thoughtful detail interviewers sometimes probe for.