1577. Two-Way Mirror Check
A necklace of beads is stored as a doubly linked list, and a jeweller wants to know whether it reads the same from both ends. Given head of a doubly linked list (each node has val, next and prev), return true if the sequence of values read from head to tail equals the sequence read from tail to head, and false otherwise. An empty list and a single-node list both count as true. Do not copy the values into an array or reverse anything: walk to the tail first, then move one pointer forward with next and the other backward with prev, comparing values until they meet or cross. The list has 0 to 1000 nodes. Aim for O(n) time and O(1) extra space.
Example 1
- Input:
- head = [1,2,3,2,1]
- Output:
- true
- Explanation:
The values read the same in both directions.
Example 2
- Input:
- head = [1,2,3]
- Output:
- false
- Explanation:
Forward 1,2,3 differs from backward 3,2,1.
Example 3
- Input:
- head = []
- Output:
- true
- Explanation:
An empty list is a mirror by definition.
Constraints
0 ≤ length ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)