LeetCode 82 - Remove Duplicates from Sorted List II

Difficulty: 🟡 Medium
Topics: Linked List, Two Pointers

Solution

Problem Understanding

This problem asks us to process a sorted singly linked list and remove every value that appears more than once. The important distinction is that we are not keeping one copy of duplicated values. Instead, every node containing a duplicated value must be removed entirely.

For example, consider the list:

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

The values 3 and 4 appear multiple times, so all nodes containing those values are removed. The final result becomes:

1 -> 2 -> 5

The input is the head node of a singly linked list. Because the list is already sorted in ascending order, duplicate values always appear next to each other. This property is extremely important because it allows us to detect duplicates by simply comparing neighboring nodes.

The output should be the head of the modified linked list after all duplicated values have been completely removed.

The constraints tell us several useful things:

The list contains at most 300 nodes, which means even less optimal solutions could still pass.
Values range from -100 to 100, but the actual values are not particularly important because the list is sorted.
Since the list is sorted, duplicate values always form contiguous groups.

Several edge cases are especially important:

The list may be empty.
The duplicates may appear at the beginning of the list.
The duplicates may appear at the end of the list.
Every node may be duplicated, resulting in an empty list.
A value may appear more than twice.
There may be no duplicates at all.

A naive implementation often fails when duplicates occur at the head because removing the head node changes the starting point of the list. This is why a dummy node is commonly used in linked list problems like this.

Approaches

Brute Force Approach

A straightforward approach is to count the frequency of every value in the linked list using a hash map.

We first traverse the entire list and store how many times each value appears. Then we perform a second traversal and rebuild the linked list using only values whose frequency is exactly one.

This approach is correct because every value with frequency greater than one is excluded from the reconstructed list.

Although this solution works well within the given constraints, it uses extra memory proportional to the number of distinct values. The problem can actually be solved using only constant extra space because the list is already sorted.

Key Insight for the Optimal Solution

The crucial observation is that the linked list is sorted. Since duplicate values always appear consecutively, we can detect duplicates during a single traversal without using additional storage.

We maintain two pointers:

A prev pointer that tracks the last confirmed unique node.
A current pointer used to scan through the list.

Whenever we encounter consecutive nodes with the same value, we skip the entire group of duplicates. Otherwise, we move prev forward.

A dummy node placed before the head simplifies handling cases where duplicates occur at the beginning of the list.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Uses a hash map to count frequencies
Optimal	O(n)	O(1)	Uses pointer manipulation on the sorted list

Algorithm Walkthrough

Create a dummy node whose next pointer points to the original head.

This dummy node helps handle cases where the first few nodes are duplicates. Without it, removing duplicated head nodes becomes awkward. 2. Initialize a prev pointer to the dummy node.

The prev pointer always represents the last node that is confirmed to be unique. 3. Initialize a current pointer to the head of the list.

This pointer scans through the linked list. 4. Traverse the list while current is not None.

At each step, determine whether the current value is duplicated. 5. Check whether current.next exists and whether it has the same value as current.

If both conditions are true, we have found a duplicate sequence. 6. Skip the entire duplicate group.

Continue moving current forward while the next node has the same value. 7. After reaching the end of the duplicate group, connect prev.next to current.next.

This removes every node with the duplicated value from the linked list. 8. If the current value is not duplicated, move prev forward.

This means the current node is safe to keep in the final answer. 9. Move current forward to continue traversal. 10. Return dummy.next.

The actual head may have changed if the original head was duplicated.

Why it works

The algorithm maintains the invariant that all nodes before prev are guaranteed to be unique and correctly connected. Whenever a duplicate group is found, the entire group is skipped and excluded from the list. Since the input list is sorted, all duplicates appear consecutively, so no duplicate value can be missed. By the time traversal finishes, every duplicated value has been removed exactly once.

Python Solution

# 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)
        dummy.next = head

        prev = dummy
        current = head

        while current:
            if current.next and current.val == current.next.val:
                duplicate_value = current.val

                while current and current.val == duplicate_value:
                    current = current.next

                prev.next = current
            else:
                prev = current
                current = current.next

        return dummy.next

The implementation begins by creating a dummy node that points to the head. This simplifies deletion logic, especially when the first nodes are duplicates.

The prev pointer tracks the last node that should remain in the final list. The current pointer scans through the linked list.

Inside the loop, the code checks whether the current node starts a duplicate sequence. If so, it stores the duplicated value and skips every node containing that value. After the duplicate group is skipped, prev.next is updated to bypass the removed nodes.

If the current node is not duplicated, it is part of the final answer, so both pointers move forward normally.

Finally, the function returns dummy.next, which points to the updated head of the linked list.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}

    prev := dummy
    current := head

    for current != nil {
        if current.Next != nil && current.Val == current.Next.Val {
            duplicateValue := current.Val

            for current != nil && current.Val == duplicateValue {
                current = current.Next
            }

            prev.Next = current
        } else {
            prev = current
            current = current.Next
        }
    }

    return dummy.Next
}

The Go implementation follows exactly the same logic as the Python version.

The primary difference is pointer syntax and nil handling. Go uses explicit pointer types, so nodes are manipulated through *ListNode. The dummy node is allocated using a struct literal.

Because Go does not have Python's dynamic typing or automatic None handling, every pointer dereference must be carefully checked against nil before accessing fields like Next or Val.

No integer overflow concerns exist here because node values remain within small constraints.

Worked Examples

Example 1

Input:

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

Initial state:

prev	current	List
dummy	1	dummy -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5

Step 1:

1 is not duplicated.

Move both pointers forward.

prev	current
1	2

Step 2:

2 is not duplicated.

prev	current
2	3

Step 3:

3 is duplicated because the next node is also 3.

Skip the entire duplicate group.

prev	current after skipping
2	4

Reconnect:

2 -> 4

Step 4:

4 is duplicated because the next node is also 4.

Skip the entire duplicate group.

prev	current after skipping
2	5

Reconnect:

2 -> 5

Step 5:

5 is unique.

Move forward and finish traversal.

Final result:

1 -> 2 -> 5

Example 2

Input:

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

Initial state:

prev	current
dummy	1

Step 1:

1 is duplicated.

Skip all nodes containing 1.

prev	current after skipping
dummy	2

Reconnect:

dummy -> 2

Step 2:

2 is unique.

prev	current
2	3

Step 3:

3 is unique.

Traversal ends.

Final result:

2 -> 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited at most once
Space	O(1)	Only a few pointers are used

The algorithm performs a single linear traversal of the linked list. Even when skipping duplicates, each node is processed only once overall. No auxiliary data structures proportional to input size are used, so the extra space remains constant.

Test Cases

# Helper functions for testing

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

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

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

    return dummy.next

def linked_list_to_list(head):
    result = []

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

    return result

class Solution:
    def deleteDuplicates(self, head):
        dummy = ListNode(0)
        dummy.next = head

        prev = dummy
        current = head

        while current:
            if current.next and current.val == current.next.val:
                duplicate_value = current.val

                while current and current.val == duplicate_value:
                    current = current.next

                prev.next = current
            else:
                prev = current
                current = current.next

        return dummy.next

solution = Solution()

# Provided example with duplicates in middle
head = build_list([1, 2, 3, 3, 4, 4, 5])
assert linked_list_to_list(solution.deleteDuplicates(head)) == [1, 2, 5]

# Provided example with duplicates at start
head = build_list([1, 1, 1, 2, 3])
assert linked_list_to_list(solution.deleteDuplicates(head)) == [2, 3]

# Empty list
head = build_list([])
assert linked_list_to_list(solution.deleteDuplicates(head)) == []

# No duplicates
head = build_list([1, 2, 3, 4])
assert linked_list_to_list(solution.deleteDuplicates(head)) == [1, 2, 3, 4]

# All elements duplicated
head = build_list([1, 1, 2, 2, 3, 3])
assert linked_list_to_list(solution.deleteDuplicates(head)) == []

# Single node
head = build_list([1])
assert linked_list_to_list(solution.deleteDuplicates(head)) == [1]

# Duplicates at end
head = build_list([1, 2, 3, 3])
assert linked_list_to_list(solution.deleteDuplicates(head)) == [1, 2]

# Duplicates at beginning
head = build_list([1, 1, 2, 3])
assert linked_list_to_list(solution.deleteDuplicates(head)) == [2, 3]

# Multiple duplicate groups
head = build_list([1, 1, 2, 3, 3, 4, 5, 5])
assert linked_list_to_list(solution.deleteDuplicates(head)) == [2, 4]

# Negative numbers
head = build_list([-3, -3, -2, -1, -1, 0])
assert linked_list_to_list(solution.deleteDuplicates(head)) == [-2, 0]

Test	Why
`[1,2,3,3,4,4,5]`	Validates standard duplicate removal
`[1,1,1,2,3]`	Ensures duplicates at head are handled
`[]`	Confirms empty input works
`[1,2,3,4]`	Confirms unique lists remain unchanged
`[1,1,2,2,3,3]`	Ensures all nodes can be removed
`[1]`	Validates single-node input
`[1,2,3,3]`	Tests duplicates at tail
`[1,1,2,3]`	Tests duplicates at beginning
`[1,1,2,3,3,4,5,5]`	Tests multiple duplicate groups
`[-3,-3,-2,-1,-1,0]`	Confirms negative values work correctly

Edge Cases

Empty List

An empty list is represented by head = None. This case can easily cause null pointer errors in linked list problems if pointer access is not carefully guarded.

The implementation handles this naturally because the traversal loop only runs while current exists. If the list is empty, the loop never executes and dummy.next correctly returns None.

Duplicates at the Beginning

Cases like:

1 -> 1 -> 2 -> 3

are tricky because the head itself must be removed. Many naive solutions fail because they lose track of the new head.

The dummy node solves this problem cleanly. Since prev starts at the dummy node, reconnecting prev.next after skipping duplicates correctly updates the head of the resulting list.

Entire List Removed

A case such as:

1 -> 1 -> 2 -> 2

results in an empty final list.

This is another situation where the dummy node is important. After all duplicate groups are skipped, dummy.next becomes None, which correctly represents an empty linked list.

Duplicate Groups Larger Than Two

Some implementations incorrectly assume duplicates appear exactly twice. However, inputs like:

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

contain larger duplicate groups.

The inner loop continues advancing until the value changes, ensuring every occurrence of the duplicated value is removed regardless of group size.