Remove Duplicates from Sorted List II

Mediumlinked-listtwo-pointers
Category: Linked List
Companies that ask this question:
AmazonMicrosoftBloomberg
LeetCode →NeetCode →

Approach

Remove Duplicates from Sorted List II

Problem Statement

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

Return the linked list sorted as well.

Note: Unlike Remove Duplicates I, we remove ALL occurrences of duplicates, not just keep one.

Approach: Dummy Node + Two Pointers

Use a dummy node and track the previous non-duplicate node.

Algorithm

  1. Create Dummy: Use dummy node to handle edge cases
  2. Traverse with prev pointer: Keep prev pointing to last confirmed non-duplicate
  3. Detect duplicates: If current.val == current.next.val, it's a duplicate
  4. Skip all duplicates: Move forward until value changes
  5. Connect: Link prev to first non-duplicate node

Time Complexity

  • Time: O(n) - single pass through the list
  • Space: O(1) - only pointers

Example

Input: 1→2→3→3→4→4→5

Step 1: 1 is unique, keep it
  prev→1, check 2

Step 2: 2 is unique, keep it
  prev→2, check 3

Step 3: 3 appears twice, remove both
  Skip 3→3, prev still at 2

Step 4: 4 appears twice, remove both
  Skip 4→4, prev still at 2

Step 5: 5 is unique, keep it
  prev→5

Result: 1→2→5

Key Insights

  1. Dummy node simplifies head handling
  2. Must check if current == next BEFORE moving
  3. Remove ALL occurrences, not just extras
  4. prev only advances when node is confirmed unique
  5. Must handle edge cases: all duplicates, no duplicates

Solution

java
1/**
2 * Remove Duplicates from Sorted List II
3 * Time: O(n), Space: O(1)
4 */
5
6class ListNode {
7    int val;
8    ListNode next;
9    ListNode() {}
10    ListNode(int val) { this.val = val; }
11    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
12}
13
14class Solution {
15    public ListNode deleteDuplicates(ListNode head) {
16        ListNode dummy = new ListNode(0);
17        dummy.next = head;
18        ListNode prev = dummy;
19        
20        while (head != null) {
21            if (head.next != null && head.val == head.next.val) {
22                while (head.next != null && head.val == head.next.val) {
23                    head = head.next;
24                }
25                prev.next = head.next;
26            } else {
27                prev = prev.next;
28            }
29            
30            head = head.next;
31        }
32        
33        return dummy.next;
34    }
35}
36
Loading visualizer...