56. Palindrome Linked List
Decide whether the sequence of node values reads the same from the head toward the tail as it does in reverse. The optimized approach must use constant auxiliary workspace.
If links are temporarily rearranged while checking, restore every original link before returning. Repeated values alone do not imply that the entire sequence is a palindrome.
Example 1
Input
N0(1)→N1(2)→N2(2)→N3(1)
Output
true; original links restored
Explanation: Compare 1 with 1 and 2 with 2 after reversing N2→N3, then reverse back.
Example 2
Input
N0(1)→N1(2)→N2(3)→N3(4)→N4(1)
Output
false; original links restored
Explanation: The outside pair matches but the second pair 2/4 fails. The implementation records false and still restores.
Example 3
Input
null
Output
true
Explanation: No values violate the mirror condition and there are no links to restore.
Constraints
0 <= nodes per input list <= 105-231 <= node.value <= 231 - 1- Inputs may be null. Lists are acyclic unless this problem explicitly detects a cycle.
Hints
Hint 1
How can the end-to-middle values be made available in forward traversal?
Hint 2
Reverse just the second half and compare only as many pairs as that half contains.
Hint 3
Retain its reversed root, record mismatches, reverse back and reconnect before returning.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Even palindrome and full restoration
[1,2,2,1]
true