Bus Stop Echo Trimming
Keep only the first and last nodes of each equal-value linked list run
A city bus records its stop identifiers in a singly linked list. While the bus waits at a stop, the recorder may write the same identifier repeatedly. Identifiers can be negative when they refer to temporary stops.
The archive must preserve the arrival and departure records for each uninterrupted visit:
- A run is a maximal sequence of consecutive nodes with the same value.
- If a run contains one node, keep that node.
- If a run contains two or more nodes, keep its first and last nodes and remove every node between them.
Given the head head, modify the linked list in place and return its head. Preserve the order and values of all retained nodes, and reuse the original nodes rather than creating replacements.
Separate visits to the same stop remain separate runs if another stop appears between them. If the list is empty, return null.
Examples
Example 1
Input: head = [4,4,4,4,9,-2,-2,-2] Output: [4,4,9,-2,-2]
The run of four records for stop 4 retains its first and last records. The single record for stop 9 stays unchanged, and the three records for stop -2 retain their endpoints.
Example 2
Input: head = [3,3,8,3,3] Output: [3,3,8,3,3]
Every run already has at most two records, so no nodes are removed. The two visits to stop 3 remain separate because stop 8 appears between them.
Example 3
Input: head = [7,7,7,7,7] Output: [7,7]
The entire list is one run. Only its first and last nodes are retained.
Constraints
- The list contains between 0 and 10,000 nodes.
- -1,000,000 <= node.val <= 1,000,000.
- The linked list has no cycle.
- Reuse the original nodes and modify only their next pointers.
The intended solution takes O(n) time and O(1) auxiliary space. Linked lists are serialized as arrays of node values; an empty list is serialized as [].
Hints
Show hint 1Hint 1
Process one maximal run at a time, keeping a pointer to its first node.
Show hint 2Hint 2
After locating the last node of a run, connect the first node directly to it when they are different nodes.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you change the algorithm to retain only the first node of each run?
- How would you retain the first and last k nodes of each run, keeping every node when those portions overlap?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem