LeetCode 82: Remove Duplicates from Sorted List II in Go

Programming & Development / April 8, 2025

LeetCode 82: Remove Duplicates from Sorted List II in Go – Clean Linked List Manipulation

Go Golang LeetCode Linked List Remove Duplicates Sorted List Two Pointers Dummy Node Edge Cases ListNode Linked List Algorithm

Copy Link Bookmark Print

Introduction

In LeetCode 82: Remove Duplicates from Sorted List II, you’re given a sorted linked list and asked to remove all nodes with duplicate values, leaving only distinct numbers from the original list.

Unlike LeetCode 83 (which removes extra duplicates but keeps one), this problem requires all duplicates to be deleted—making it slightly more complex and more interesting.

Problem Statement

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers.

Return the linked list sorted as well.

Example:

go

Input: 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
Output: 1 -> 2 -> 5

Input: 1 -> 1 -> 1 -> 2 -> 3
Output: 2 -> 3

Approach: Dummy Node + Two Pointers

Strategy:

Use a dummy node that points to the head (helps with edge cases).
Use a pointer prev to track the last node before duplicates.
Use pointer curr to scan through the list.
If a duplicate is detected (curr.Val == curr.Next.Val), skip all nodes with that value.
Otherwise, move prev forward to curr.

This avoids retaining any duplicated values.

Go Implementation

go

type ListNode struct {
    Val  int
    Next *ListNode
}

func deleteDuplicates(head *ListNode) *ListNode {
    dummy := &ListNode{0, head}
    prev := dummy

    for head != nil {
        // If it's the start of duplicates
        if head.Next != nil && head.Val == head.Next.Val {
            // Skip all nodes with this value
            for head.Next != nil && head.Val == head.Next.Val {
                head = head.Next
            }
            // Connect prev to node after duplicates
            prev.Next = head.Next
        } else {
            prev = prev.Next
        }
        head = head.Next
    }

    return dummy.Next
}

Explanation

Dummy node handles edge cases where the head itself might be removed.
Inner loop skips over all nodes with a duplicate value.
prev.Next = head.Next ensures that all duplicates are removed in one step.
Returns the head of the filtered list.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

Where n is the number of nodes in the list.

Edge Cases

All values are duplicates → result is nil.
No duplicates → entire list is preserved.
Duplicates only at beginning or end → dummy node helps avoid null pointer issues.

Conclusion

LeetCode 82 is a brilliant application of linked list traversal and careful pointer updates. Using a dummy node and two pointers is the key pattern here. It’s especially useful in interviews to show mastery over:

NUHMAN.com