83. Remove Duplicates from Sorted List

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

The problem

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Pattern

Remove Duplicates from Sorted List 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 input is a sorted linked list, think about how duplicates appear consecutively and how that can simplify your approach.
2. Try traversing the list once and compare each node's value with the value of the next node to identify duplicates.
3. When you find consecutive nodes with the same value, consider how you can modify the links to skip over duplicate nodes without creating new nodes.

Complexity

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

Asked at

Remove Duplicates from Sorted List has been reported in interviews at Amazon, Adobe, Goldman Sachs, Qualcomm.