Chain Reads the Same Both Ways
EasyLinked List
Problem
A DNA fragment is stored as a singly linked list of integer codes. Biologists want to know whether the fragment is symmetric.
Given the head, return true if the sequence of values reads the same from front to back as from back to front, and false otherwise. Try to use O(1) extra space.
Example 1
- Input:
- head = [1, 2, 3, 2, 1]
- Output:
- true
Read backwards it is still 1, 2, 3, 2, 1.
Example 2
- Input:
- head = [1, 2, 2, 3]
- Output:
- false
Constraints
- 0 ≤ number of nodes ≤ 10^5
- 0 ≤ node.val ≤ 9
Hint
Show the first hint
Copying the values into an array makes this trivial. What would let you compare without the copy?
Walkthrough
How to approach it
01Clarify before coding
- Is an empty list symmetric? Yes, return true; so is a single node.
- May I modify the list? Yes for this exercise, though restoring it afterwards is good practice.
- Is O(n) extra memory acceptable? It works, but the target is O(1).
02Brute force
Copy the values into an array and compare it with its reverse (or use two indices).
Cost: O(n) time and O(n) space: correct, but the follow-up always asks for constant space.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.