LeetCode #83 Easy

Remove Duplicates from Sorted List

Delete duplicates from a sorted list so each value appears once.

linked-list

02

Intuition

The instinct is to reach for a set of seen values, which works and is also the wrong lesson: the list is SORTED, so equal values are already neighbours and a set is memory you never needed. Compare each node against the one directly ahead of it and you have everything a set would have told you. The real slip is the pointer discipline. When you delete cur.next because it matches, the following node moves into that slot and might match too, so you must stay on cur and check again - advance unconditionally and [1,1,1] comes back as [1,1]. Note this problem keeps ONE copy of each value, unlike its harder sibling which removes every value that was ever duplicated; that difference decides whether a dummy node is needed at all. Here it is not, because the head is always kept.

How to spot this pattern

Because the list is sorted, duplicates are adjacent — so comparing each node to its immediate successor is enough. No dummy head is needed here, since the first node is always kept.

03

Approach

1

Lean on the sorting

In a sorted list every group of equal values is contiguous. That means a single forward pass comparing cur.val with cur.next.val sees every duplicate, and no auxiliary structure is required. Recognising when the input's ordering already encodes the information is the transferable part.

2

Delete without advancing

If cur.next.val == cur.val, splice with cur.next = cur.next.next and loop again from the same cur. Only advance when the next value differs. Advancing after every step is the bug that leaves one duplicate behind in a run of three or more.

3

Return the original head

The head is always kept - it is the first occurrence of its own value - so no dummy node is needed and head is still correct at the end. This is the one case in the deletion family where you can safely skip the dummy.

04

Solution & live demo

▶1class Solution:
▶2    def deleteDuplicates(self, head):
▶3        cur = head
▶4        while cur and cur.next:
▶5            if cur.next.val == cur.val:
▶6                cur.next = cur.next.next
▶7            else:
▶8                cur = cur.next
▶9        return head

05

Common pitfalls

Advancing after unlinking

✗ Wrong

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

✓ Right

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

Three or more equal values in a row need repeated unlinking from the same position. Advancing unconditionally skips past the newly linked node and leaves a duplicate.

Adding a dummy head

✗ Wrong

dummy = ListNode(0)
dummy.next = head

✓ Right

cur = head

Harmless but unnecessary — unlike the remove-by-value problem, the head is never deleted here because it's the first occurrence of its value. The dummy adds a node and a return-value subtlety for nothing.

Checking only cur in the loop condition

✗ Wrong

while cur:

✓ Right

while cur and cur.next:

The body dereferences cur.next.val, so the successor must exist. Testing only cur throws on the final node.

06

Edge cases

All values identical

Collapses to a single node.

No duplicates

The pointer advances every step and the list is unchanged.

Run of three or more

Staying on cur after a deletion collapses the whole run.

Empty or single node

The loop condition fails immediately; return head.

07

Complexity

Time

O(n)

Space

O(1)

One pass, no set. Sorting is what buys the O(1) space.