LeetCode 83: Remove Duplicates from Sorted List

Problem Restatement

We are given the head of a sorted linked list.

We need to delete duplicate values so that each value appears only once.

Unlike LeetCode 82, we do not remove all copies of a duplicated value. We keep one copy.

For example:

1 -> 1 -> 2

becomes:

1 -> 2

The official statement says to delete duplicates so that each element appears only once, then return the sorted linked list. The constraints are 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, 1, 2]

The value 1 appears twice.

Keep one 1.

Answer:

[1, 2]

Example 2:

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

The value 1 appears twice, and the value 3 appears twice.

Keep one copy of each.

Answer:

[1, 2, 3]

Example 3:

head = []

There are no nodes.

Answer:

[]

First Thought: Use a Set

A common idea is to store values we have already seen.

While walking through the list, if a value already exists in the set, remove that node.

This works for many duplicate-removal problems, but here we can do better.

The list is sorted. That means duplicate values are always adjacent.

So we do not need a set.

Key Insight

Because the list is sorted, equal values appear next to each other.

Example:

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

The duplicates form consecutive groups:

[1, 1, 1], [2], [3, 3]

To keep one copy of each value, we only need to compare a node with its next node.

If:

cur.val == cur.next.val

then cur.next is a duplicate and should be skipped.

We remove it by rewiring:

cur.next = cur.next.next

If the values are different, then cur is the last copy of its value, so we can move forward.

Algorithm

Use one pointer:

cur = head

While both cur and cur.next exist:

1. If cur.val == cur.next.val, remove cur.next.
2. Otherwise, move cur forward.
3. Return head.

The important detail is that we do not move cur after removing a duplicate.

For example:

1 -> 1 -> 1 -> 2

After removing the second 1, the list becomes:

1 -> 1 -> 2

The current node is still 1, and the next node is still a duplicate. So we must check again.

Walkthrough

Use:

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

Start:

cur = first 1

Compare cur with cur.next:

1 == 1

The next node is a duplicate, so skip it:

cur.next = cur.next.next

The list becomes:

1 -> 2 -> 3 -> 3

Now compare:

1 != 2

Move cur to 2.

Compare:

2 != 3

Move cur to 3.

Compare:

3 == 3

Skip the duplicate 3.

The list becomes:

1 -> 2 -> 3

Now cur.next is None, so stop.

Return the original head.

Correctness

The algorithm keeps the first node of each value group.

Since the list is sorted, all duplicate copies of a value appear immediately after the first copy.

When cur.val == cur.next.val, cur.next is an extra copy of the same value. Rewiring cur.next = cur.next.next removes that duplicate while keeping one copy at cur.

When cur.val != cur.next.val, there are no more copies of cur.val after cur, because any equal values would have to be adjacent in a sorted list. Therefore, it is safe to move cur forward.

The loop continues until every adjacent pair has been checked or removed. At the end, no two adjacent nodes have the same value. Since the list is sorted, that means no value appears more than once.

Therefore, the returned list contains each original value exactly once.

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]:
        cur = head

        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next

        return head

Code Explanation

Start at the head:

cur = head

The loop needs both the current node and the next node:

while cur and cur.next:

If the next node has the same value, skip it:

if cur.val == cur.next.val:
    cur.next = cur.next.next

We do not move cur in this case, because there may be more duplicates after the removed node.

If the next value is different, move forward:

else:
    cur = cur.next

Finally, return the original head:

return head

This works even when head is None.

Testing

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, 1, 2], [1, 2])
    check([1, 1, 2, 3, 3], [1, 2, 3])
    check([], [])
    check([1], [1])
    check([1, 1, 1], [1])
    check([1, 2, 3], [1, 2, 3])
    check([-3, -3, -1, 0, 0, 2], [-3, -1, 0, 2])

    print("all tests passed")

run_tests()

Test meaning: