PPractick

The problem

A DNA-sequence tool stores bases in a singly linked list and must check whether a sequence reads the same forwards and backwards. With an array you'd compare from both ends, but a singly linked list can't walk backwards. Copying the values to an array is O(n) extra space. The O(1)-space technique combines three earlier building blocks: find the middle with fast and slow pointers, reverse the second half in place, compare the two halves node by node, and then restore the list so the caller's data isn't left scrambled.

Example: 1 -> 2 -> 2 -> 1 → true; 1 -> 2 → false.

Function signature

bool isPalindrome(Node* head);  // O(1) extra space; the list is restored before returning

Test cases

Input list	Output	Explanation
1 -> 2 -> 2 -> 1	true	Even length
1 -> 2 -> 3 -> 2 -> 1	true	Odd length: the middle is ignored
1 -> 2	false
1 -> 2 -> 3	false
1	true
(empty)	true

(Confirm: compare values; O(1) extra space is expected; the list must be unchanged after the check.)

How interviewers phrase it

• "Check whether a singly linked list is a palindrome" (LeetCode 234).
• "Can you do it in O(n) time and O(1) space?"

Clarifying questions to ask

1. May I modify the list temporarily? Must it be restored?
2. Is O(1) extra space required?
3. How long can the list be? (Recursion-based solutions use O(n) stack.)

Follow-ups to expect

1. "What's the easy approach?"
2. "How do you find where the second half starts?"
3. "How is the odd-length middle handled?"
4. "Why restore the list?"
5. "Complexity?"

Related questions

• Detect a loop in LL Medium
• Find the starting point in LL Medium
• Length of loop in LL Medium
• Remove Nth node from the back of the LL Medium
• Delete the middle node in LL Medium
• Find the intersection point of Y LL Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in