Remove Duplicates from Sorted List — Single Pass Pointer Walk Explained

Problem Statement#

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.

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]

Example 2:

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

Example 3:

Input:  head = []
Output: []

Why This Problem Matters#

Remove Duplicates from Sorted List (LeetCode 83) is an Easy-rated problem that every candidate should be able to solve in under five minutes. Bloomberg and Microsoft use it as a screening problem for this exact reason — it's a baseline check for pointer comfort. If you need more than a few minutes or make pointer errors here, the interviewer flags it as a concern for medium-difficulty problems.

The problem also introduces the key concept of "in-place pointer manipulation on a sorted structure." The sorted property is the critical enabler: you don't need a hash set to detect duplicates because any duplicate must appear consecutively. This is a pattern that appears across many interview problems — when a structure is sorted, consecutive comparison replaces random lookup.

Understanding why and how this works prepares you for the harder variant, LeetCode 82 (Remove Duplicates from Sorted List II), where you must remove all nodes that have any duplicates — not just the extra copies. The harder version requires a dummy head node and more careful skip logic, but the same sorted-means-consecutive-duplicates intuition applies.

The Core Insight#

Because the list is sorted, any duplicate values must be adjacent. You only need to look one step ahead from the current node. If curr.val == curr.next.val, skip curr.next by setting curr.next = curr.next.next. Do not advance curr — there might be more duplicates. If curr.val != curr.next.val, advance curr to the next distinct node.

This is a single-pass O(n) algorithm with O(1) space. The head of the list never changes (the first occurrence of any value is kept), so you return the original head unchanged.

Visual Dry Run#

Input: 1 -> 1 -> 2 -> 3 -> 3 -> None

Output: 1 -> 2 -> 3 -> None

Notice: when we removed a duplicate, we stayed on the same curr node and checked again before advancing. This handles runs of three or more duplicates (e.g., 1 -> 1 -> 1).

Solution (Optimal)#

Python#

def deleteDuplicates(head):
    curr = head
    while curr and curr.next:
        if curr.val == curr.next.val:
            curr.next = curr.next.next  # skip the duplicate
            # do NOT advance curr — check again for triple duplicates
        else:
            curr = curr.next  # distinct value, move forward
    return head  # head never changes — first node is always kept

Time complexity: O(n) — each node is visited at most once.

Space complexity: O(1) — only one pointer variable.

JavaScript#

var deleteDuplicates = function(head) {
    let curr = head;
    while (curr !== null && curr.next !== null) {
        if (curr.val === curr.next.val) {
            curr.next = curr.next.next;  // skip duplicate
        } else {
            curr = curr.next;            // move to next distinct
        }
    }
    return head;
};

Complexity:

Why we return head directly (no dummy needed): Unlike problems that might delete the head node (e.g., remove all nodes with value X), this problem always keeps the first occurrence of every value. The head node's value is unique (it's the smallest element, and its first occurrence is always kept), so head remains unchanged.

Common Mistakes#

1. Advancing curr after skipping a duplicate. If you write curr.next = curr.next.next and then immediately curr = curr.next, you might miss additional duplicates. For example, in 1 -> 1 -> 1, after the first skip you'd be at the second 1 and incorrectly advance past the third. Always re-check before advancing.

2. Using the loop condition while curr instead of while curr and curr.next. Inside the loop, you access curr.next.val. If curr.next is None, this throws an error. The curr.next guard in the while condition prevents this.

3. Confusing this with LeetCode 82. LC 83 keeps one copy of each duplicate value. LC 82 removes all occurrences of any value that appears more than once. These are different problems — re-read carefully.

4. Trying to use a dummy head. A dummy head is unnecessary here because the head never changes. Adding one doesn't break correctness, but it adds unnecessary complexity and is a signal that you misread the problem.

5. Not handling the empty list. If head is None, curr starts as None, the while condition is immediately false, and you return None. This is correct and automatic — but verify you don't access curr.val before the while check.

Interview Tips#

1. State the key observation immediately: "The list is sorted, so duplicates are always adjacent. I only need to compare each node with its immediate neighbor."

2. Walk through an example with triple duplicates like [1, 1, 1, 2] to demonstrate you handle runs — not just pairs.

3. Explain why no dummy node is needed — it shows attention to detail: "The head is always kept, so I can return head directly."

4. Anticipate the follow-up: "If the interviewer says 'now delete all nodes that have duplicates' — that's LC 82. I'd add a dummy head and use different skip logic."

5. Code this in 2-3 minutes — it should be that fast. If it takes longer, practice until it's automatic.

Follow-up Questions#

Q: What if you need to remove ALL occurrences of duplicate values (LC 82)? You need a dummy head node and a previous pointer. When you detect a duplicate value, you skip all nodes with that value (not just the extras). This requires checking prev.next = curr.next after the skip loop.

Q: What if the list is not sorted? You'd need a hash set to detect duplicates seen so far, making it O(n) time and O(n) space. With an unsorted list, consecutive comparison no longer works.

Q: Can you do this recursively? Yes. deleteDuplicates(head) returns: if head and head.next have the same value, return deleteDuplicates(head.next) (skip current head). Otherwise, head.next = deleteDuplicates(head.next) and return head. Elegant but O(n) stack space.

Q: What if there are duplicates at the very end (e.g., [1, 2, 2])? Handled correctly. When curr is at the first 2 and curr.next is the second 2, you set curr.next = curr.next.next = None. The loop then sees curr.next is None and exits. The list becomes 1 -> 2.

Key Takeaways#

• The sorted property is the key: duplicates are always adjacent, so you only compare curr with curr.next — no hash set needed.
• When values match, skip curr.next but do not advance curr — there may be more duplicates in a run.
• Return the original head — it's never deleted in this problem variant.
• The loop condition while curr and curr.next prevents null pointer errors.
• This is the simpler sibling of LC 82 — know both variants and be ready to explain the difference.
• Time is O(n), space is O(1) — a single pass with no auxiliary data structures.