AlgoMaster Logo

Remove Duplicates from Sorted List

Last Updated: March 29, 2026

easy

Understanding the Problem

We have a linked list where nodes are already sorted in ascending order. Some nodes have duplicate values, and we need to remove the extra copies so that each value appears exactly once. The output should still be a sorted linked list.

This is the linked list equivalent of "Remove Duplicates from Sorted Array." The same core idea applies: because the list is sorted, all duplicates are grouped together. We never need to look far to detect whether a node is a duplicate. We just compare each node with the one right next to it. If they share the same value, the next node is a duplicate and we can skip over it by adjusting pointers.

The key difference from the array version is that we don't need a separate "insert position" pointer. With linked lists, removing an element is just a matter of relinking the next pointer. No shifting, no overwriting.

Key Constraints:

  • 0 <= number of nodes <= 300 → The list can be empty (0 nodes), so we need a null check upfront. With n at most 300, any O(n) or even O(n^2) approach is fast enough.
  • -100 <= Node.val <= 100 → Small value range (201 distinct values). We could use a hash set to track seen values, but since the list is sorted, a simple neighbor comparison is cleaner and uses no extra space.
  • Sorted in ascending order → This is the critical constraint. Duplicates are always consecutive, so comparing current.val with current.next.val is enough to detect them.

Approach 1: Using a Hash Set

Intuition

The most obvious way to remove duplicates from any collection: use a hash set to track which values we've already seen. Walk through the list, and for each node, check if its next node's value is in the set. If it is, skip that node. If not, add the value to the set and keep the node.

This approach ignores the fact that the list is sorted. It works on unsorted lists too, which makes it a valid but wasteful starting point for this problem.

Algorithm

  1. If the list is empty, return null.
  2. Create a hash set and add the head node's value to it.
  3. Walk through the list, keeping track of the current node.
  4. For each node, if its next node's value is already in the set, remove the next node by setting current.next = current.next.next.
  5. If the next node's value is new, add it to the set and move current forward.
  6. Return the head.

Example Walkthrough

1Initialize: seen={1}, current=node(1)
1
current
1
2
3
3
null
1/6

Code

Since the list is sorted, duplicates are always adjacent. Can we detect and remove them using only a neighbor comparison, without any extra data structure?

Approach 2: Single Pass In-Place (Optimal)

Intuition

Here's the thing about sorted linked lists: duplicates always sit right next to each other. So we don't need a hash set to remember which values we've encountered. We just need to compare each node with the one directly after it.

The algorithm is beautifully simple. Walk through the list with a single pointer. At each node, look at its next neighbor. If they share the same value, the neighbor is a duplicate, so we skip over it by relinking the pointer. If they have different values, we move forward.

Algorithm

  1. If the list is empty, return null.
  2. Start with a pointer current at the head.
  3. While current and current.next both exist:
    • If current.val == current.next.val, skip the next node by setting current.next = current.next.next.
    • Otherwise, move current forward to current.next.
  4. Return the head.

Example Walkthrough

1Initialize: current = node(1)
1
current
1
2
3
3
null
1/6

Code