Algorithm

Remove Duplicates from Sorted List

Linked List Pattern

Remove Duplicates from Sorted List

Given the head of a sorted (ascending) linked list, delete nodes so that each distinct value appears exactly once, keeping one copy of each. The result stays sorted. Modify the list in place and return its head — the head value is the smallest, so it is never the copy that gets removed, and the head pointer is unchanged. An empty list returns an empty list.

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.
EXAMPLE 1
Input: head = [1,1,2]
Output: [1,2]
The value 1 appears twice in a row; one copy is kept and the repeat removed, leaving each distinct value once, still in sorted order.
EXAMPLE 2
Input: head = [1,1,2,3,3]
Output: [1,2,3]
Two separate runs of duplicates (the 1s and the 3s) each collapse to a single copy, so the surviving distinct values are 1, 2, 3.
EXAMPLE 3
Input: head = [1,1,1]
Output: [1]
All three nodes share the value 1, so only one copy remains. A run longer than two still reduces to exactly one node.
Is it guaranteed all equal values are adjacent?
Yes — that follows from the list being sorted. If it weren't sorted you could not rely on adjacency, and you'd need a set of seen values (or to sort first), which costs extra space.
Do I keep one copy of each value, or remove every node that was ever duplicated?
This problem keeps one copy of each distinct value. Removing all nodes that had any duplicate is a different, harder variant (Remove Duplicates II) — worth confirming which one the interviewer means.
Should I edit node values or unlink nodes?
Unlink nodes by rewiring next pointers; leave the surviving nodes' values untouched. Rewiring is the point — it's O(1) per removal and preserves node identity.
Can the head itself get removed?
Not in this version: the head holds the smallest value and we always keep the first copy of a value, so the head pointer never changes — you can safely return the original head.
The Goal: Keeping only one of each

If you have a list like [1, 1, 2], you want it to become [1, 2]. Since the list is already sorted, we know that any identical numbers must be sitting right next to each other.

The Brute Force: Using a "Seen" List

If the list weren't sorted, we'd have to keep a separate "Seen" set in our pocket. Every time we saw a number, we'd check if it was in our set. If it was, we'd delete it. This would take O(N) extra space.

python
seen = set()
while curr:
    if curr.val in seen: delete(curr)
    else: seen.add(curr.val)
The Neighbor Check

Because our list is sorted, we don't need a "Seen" set. We just look at our immediate neighbor.
- If my neighbor has the same value as me, I "skip" them by pointing my next to my neighbor's next.
- Important: After skipping, I don't move forward yet! I stay on the same node and check my new neighbor, just in case there's another duplicate (like [1, 1, 1]).

The Pointer Logic

We use a single pointer to walk through the list. We only move it forward when we are absolutely sure our neighbor is different.

python
curr = head
while curr and curr.next:
    if curr.val == curr.next.val:
        # Neighbor is a duplicate! Point past it.
        curr.next = curr.next.next
    else:
        # Neighbor is different! Safe to move.
        curr = curr.next
return head
Worked Example:[1, 1, 2]
1
curr
→
1
→
2
→
NULL
We initialize our tracker pointer 'curr' at the head node containing 1.
1
curr
→
1
→
2
→
NULL
We compare the value of the current node (1) with its adjacent neighbor (1). Since they match, we detect a duplicate.
1
curr
→
1
→
2
→
NULL
We point our head node directly past the duplicate to 2. We stay on this node to check its new neighbor.
1
→
2
curr
→
NULL
We compare current node value 1 with neighbor 2. Since they differ, we safely move our pointer forward to 2.
Interactive Strategy Visualization

Pointer Reassignment

Optimization: O(1) Space
curr112
Current Actionnext.val == curr.val
Insight
Skipping duplicates in O(1) space
1. Check the Neighbor
We look at the current node (1) and its neighbor (1). They are the same, so we found a duplicate!
O(N) Time · O(N) Space Seen-Set
→
O(N) Time · O(1) Space Neighbor Compare