82. Remove Duplicates from Sorted List II

How to solve Remove Duplicates from Sorted List II (LeetCode 82): the approach in brief

The problem

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Pattern

Remove Duplicates from Sorted List II is a Linked List Manipulation Patterns problem, in the In-place Reversal subpattern. The pattern covers in-place reversal, merging sorted lists, reordering, and intersection detection

Master in-place linked list reversal including full reversal, partial reversal, and k-group reversal techniques.

Approach outline

1. Since the list is sorted, duplicates will be grouped together; consider how you can traverse the list to identify these groups effectively.
2. Using a dummy node before the head can simplify edge cases where the first few nodes are duplicates; think about how this helps in removing nodes safely.
3. While traversing, use pointers to detect when consecutive nodes have the same value, and skip all nodes with that value entirely.

Complexity

The reference solution runs in O(n) time and O(1) space.

Asked at

Remove Duplicates from Sorted List II has been reported in interviews at Amazon, Bloomberg.