How do you approach Remove Duplicates from Sorted List?

Because the list is sorted, all duplicates of a value sit next to each other.

What is the time complexity of Remove Duplicates from Sorted List?

Time complexity: O(n). Space complexity: O(1) extra on a real list.

What are common mistakes on Remove Duplicates from Sorted List?

Reassigning next before saving it, which loses the rest of the list. Skipping the dummy head, which forces a special case every time the real head changes. Advancing the fast pointer without checking both fast and fast.next - the null dereference only shows up on even-length lists.

gitGood.dev

← Back to problems

Remove Duplicates from Sorted List

EasyData Structures

Description

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

Note: For this problem, linked lists are represented as arrays for simplicity. The function takes the sorted list as an array and should return the deduplicated sorted array.

Example 1

Input: head = [1,1,2]

Output: [1,2]

Example 2

Input: head = [1,1,2,3,3]

Output: [1,2,3]

Example 3

Input: head = []

Output: []

Constraints

- The number of nodes in the list is in the range [0, 300]. - -100 <= Node.val <= 100 - The list is guaranteed to be sorted in ascending order.

Remove Duplicates from Sorted List: approach, complexity and pitfalls

An easy linked list problem, graded against 6 test cases (3 of them hidden).

The pattern: Linked List

Pointer manipulation - reversal, cycle detection, and merging without extra space.

Reach for it when you see: Any problem handing you a list head, especially with an O(1) space constraint.

If you are stuck

Show the 3-step hint ladder

Because the list is sorted, all duplicates of a value sit next to each other.
Keep each value only if it differs from the last value you kept.
On a real linked list: while current.next.val == current.val, skip current.next by relinking - no extra memory needed.

The optimal approach

Show the approach: Single Pass over Adjacent Pairs

Since the list is sorted, duplicates are always adjacent. Walk the list once and keep a value only when it differs from the previously kept value. On a pointer-based list you do the same thing in place: whenever `current.next.val === current.val`, splice out `current.next`.

Time: O(n)
Space: O(1) extra on a real list

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Linked List mistakes

These apply to the pattern as a whole, not just this problem.

Reassigning `next` before saving it, which loses the rest of the list.
Skipping the dummy head, which forces a special case every time the real head changes.
Advancing the fast pointer without checking both `fast` and `fast.next` - the null dereference only shows up on even-length lists.