Collapse Repeated Readings
EasyLinked List
Problem
A thermometer logs readings into a linked list sorted in non-decreasing order, and it often repeats the same reading many times in a row.
Given the head, unlink the extra copies so that every distinct value appears exactly once, and return the head of the cleaned list.
Example 1
- Input:
- head = [1, 1, 2, 3, 3, 3]
- Output:
- [1, 2, 3]
One 1, one 2 and one 3 remain.
Example 2
- Input:
- head = [4, 4, 4]
- Output:
- [4]
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -100 ≤ node.val ≤ 100
- The list is sorted in non-decreasing order.
Hint
Show the first hint
In a sorted list, where are all the copies of a value?
Walkthrough
How to approach it
01Clarify before coding
- Keep one copy or remove every repeated value entirely? Keep exactly one copy of each value.
- Is the list guaranteed sorted? Yes, so equal values are contiguous.
- Can the list be empty? Yes: return null.
02Brute force
Collect the values into a set, sort them and build a new list.
Cost: O(n log n) time and O(n) space, and it allocates new nodes instead of cleaning the given list.
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.