Distances Between Strict Linked-List Turning Points
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
A node in a singly linked list is a critical point if its value is strictly greater than both immediate neighbors or strictly less than both. The first and last nodes cannot be critical because they lack one neighbor. Return `[minDistance, maxDistance]` over pairs of distinct critical points, where distance is the difference between their positions in the list. If fewer than two critical points exist, return `[-1, -1]`. Use the supplied `ListNode* head` interface.
```cpp
class Solution {
public:
vector<int> nodesBetweenCriticalPoints(ListNode* head);
};
```
### Examples
**Example 1:**
```text
List values: [2,5,1,4,3]
Output: [1,2]
Explanation: Zero-based positions 1,2,3 are critical; nearest separation is 1 and farthest is 2.
```
**Example 2:**
```text
List values: [1,2,2,1]
Output: [-1,-1]
Explanation: Equality with a neighbor prevents either interior node from being critical.
```
### Constraints
- The list contains 2 to `10^5` nodes.
- Node values lie in `[1,10^5]`.
### Clarifying Questions
Distance is an index difference, not the number of strictly intervening nodes. Adjacent critical nodes have distance one.
```hint Inspect the structure
Among ordered critical positions, which pairs can attain the nearest and farthest separations?
```
### Reasoning checkpoints
- Apply both strict comparisons and exclude endpoints and equal-valued plateaus.
- Return the minimum and maximum positional distances over distinct critical points.
- Handle lists with zero or one critical point and retain the original list structure.
### Optional extensions
How would you justify that your selected pairs attain both distance extremes?
Overview: Distances Between Strict Linked-List Turning Points. A linked-list node is critical when its value is strictly larger than both immediate neighbors or strictly smaller than both. End nodes cannot be critical. Return [minimum distance,maximum distance] between distinct critical nodes, measuring distance as the difference in their list positions. Return [-1,-1] if fewer than two exist. Accept the original ListNode* head.
