LeetCode 82: Remove Duplicates from Sorted List II

Problem Restatement

We are given the head of a sorted linked list.

We need to delete every node whose value appears more than once.

This is stronger than keeping one copy.

If a value appears two or more times, all nodes with that value must be removed.

For example:

1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5

The values 3 and 4 are duplicated, so all 3 nodes and all 4 nodes are removed.

The result is:

1 -> 2 -> 5

The official statement says to delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. The returned list should remain sorted. Constraints include 0 <= number of nodes <= 300, -100 <= Node.val <= 100, and the list is sorted in ascending order.

Input and Output

Function shape:

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        ...

Examples

Example 1:

head = [1, 2, 3, 3, 4, 4, 5]

The values 3 and 4 appear more than once.

Remove all nodes with those values.

Answer:

[1, 2, 5]

Example 2:

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

The value 1 appears three times.

Remove all 1 nodes.

Answer:

[2, 3]

Example 3:

head = [1, 1]

The value 1 appears more than once.

Answer:

[]

First Thought: Count Frequencies

One simple way is to make two passes.

First pass:

count[value] += 1

Second pass:

keep only nodes where count[value] == 1

This works, but it uses extra space.

Because the linked list is sorted, duplicate values appear in consecutive groups. We can remove duplicate groups in one pass with constant extra space.

Key Insight

Since the list is sorted, equal values are adjacent.

So the list can be viewed as groups:

1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5

Groups:

[1], [2], [3, 3], [4, 4], [5]

We keep groups of size 1.

We remove groups of size greater than 1.

The hard part is deleting duplicates at the head.

For example:

1 -> 1 -> 1 -> 2 -> 3

The real head must change from 1 to 2.

A dummy node solves this cleanly.

dummy -> 1 -> 1 -> 1 -> 2 -> 3

The dummy node gives us a stable node before the real head, so we can rewire dummy.next if the first group must be removed.

Algorithm

Create a dummy node before head.

Use two pointers:

Start:

dummy.next = head
prev = dummy
cur = head

Then scan the list.

For each group:

1. Check whether cur has the same value as cur.next.
2. If yes, move cur until the last node of that duplicate group.
3. Remove the whole group by setting:

prev.next = cur.next

4. If no duplicate was found, move prev forward:

prev = prev.next

5. Move cur forward.

At the end, return:

dummy.next

Walkthrough

Use:

1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5

Add dummy:

dummy -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5

Start:

prev = dummy
cur = 1

Value 1 has no duplicate.

Move prev to 1.

dummy -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
        prev
             cur = 2

Value 2 has no duplicate.

Move prev to 2.

dummy -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
             prev
                  cur = 3

Value 3 has a duplicate.

Move cur to the last 3.

Then remove the whole group:

prev.next = cur.next

Now the list becomes:

dummy -> 1 -> 2 -> 4 -> 4 -> 5

prev stays at 2.

Now cur moves to 4.

Value 4 has a duplicate.

Skip all 4 nodes and rewire:

prev.next = cur.next

Now the list becomes:

dummy -> 1 -> 2 -> 5

Value 5 has no duplicate, so it stays.

Return:

dummy.next

which is:

1 -> 2 -> 5

Correctness

The list is sorted, so all nodes with the same value appear in one consecutive group.

The algorithm processes one such group at a time.

If the current group has size 1, then its value appears exactly once in the original list. The algorithm keeps it by moving prev forward to that node.

If the current group has size greater than 1, then its value is duplicated. The algorithm moves cur to the last node of that group, then connects prev.next to the node after the group. This removes every node with that duplicated value.

The dummy node ensures the same logic works when the first group is removed. In that case, prev is the dummy node, and rewiring prev.next changes the returned head.

Because every group is either kept exactly once or removed completely, and because all groups are processed in order, the final list contains exactly the values that appeared once in the original sorted list.

Therefore, the algorithm is correct.

Complexity

Let:

n = number of nodes

Implementation

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy
        cur = head

        while cur:
            has_duplicate = False

            while cur.next and cur.val == cur.next.val:
                has_duplicate = True
                cur = cur.next

            if has_duplicate:
                prev.next = cur.next
            else:
                prev = prev.next

            cur = cur.next

        return dummy.next

Code Explanation

Create a dummy node before the list:

dummy = ListNode(0, head)

Set prev to the node before the current group:

prev = dummy

Set cur to the current group start:

cur = head

For every group, we first assume no duplicate has been found:

has_duplicate = False

Then we walk through all nodes with the same value:

while cur.next and cur.val == cur.next.val:
    has_duplicate = True
    cur = cur.next

If a duplicate group was found, remove the whole group:

if has_duplicate:
    prev.next = cur.next

prev does not move, because the next group may also need to be removed.

If the group was unique, keep it and advance prev:

else:
    prev = prev.next

Then move to the next group:

cur = cur.next

Finally, return the real head after all rewiring:

return dummy.next

Testing

The helpers below make local testing easier.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    cur = dummy

    for value in values:
        cur.next = ListNode(value)
        cur = cur.next

    return dummy.next

def to_list(head):
    values = []

    while head:
        values.append(head.val)
        head = head.next

    return values

def check(values, expected):
    s = Solution()
    head = build_list(values)
    result = s.deleteDuplicates(head)
    assert to_list(result) == expected

def run_tests():
    check([1, 2, 3, 3, 4, 4, 5], [1, 2, 5])
    check([1, 1, 1, 2, 3], [2, 3])
    check([1, 1], [])
    check([1], [1])
    check([], [])
    check([1, 2, 2], [1])
    check([1, 1, 2], [2])
    check([1, 2, 3], [1, 2, 3])

    print("all tests passed")

run_tests()

Test meaning: