visual walkthrough
Remove Duplicates from Sorted List
Basic pointer skipping on sorted data.
The idea
In a sorted list, duplicates are neighbours. So each node only needs to look at the one right after it.
To delete a node from a linked list, point the node before it past it: one arrow changes, nothing shifts.
Complexity
| approach | time | space |
|---|---|---|
| Build a new list | O(n) | O(n) |
| Skip in place | O(n) | O(1) |