Palindrome Linked List

Problem Determine whether a singly linked list is a palindrome in O(n) time and O(1) space.

Input / Output

• Input: head of singly linked list.
• Output: boolean.

Constraints

• Up to 10^5 nodes; the array-copy solution is O(n) space — the O(1)-space version is the ask.

Example

• 1→2→2→1 → true; 1→2 → false.

Expected approach

• Fast/slow pointers find the middle; reverse the second half in place; walk both halves comparing values; optionally re-reverse to restore the list (mention restoration — interviewers care). Odd length: the middle node belongs to neither half. O(n)/O(1). Alternatives to name: stack of first half (O(n) space), recursion with an outer pointer (O(n) stack).