Remove Duplicates from Sorted List II - Practice Coding Problems

Remove Duplicates from Sorted List II - Problem

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.

For example, given 1→2→3→3→4→4→5, return 1→2→5.

Unlike the original "Remove Duplicates" problem which keeps one copy of each duplicate, this problem removes all occurrences of duplicated values completely.

Input & Output

Example 1 — Basic Case with Duplicates

$ Input: head = [1,2,3,3,4,4,5]

› Output: [1,2,5]

💡 Note: Values 3 and 4 appear twice, so remove all occurrences. Keep only unique values 1, 2, and 5.

Example 2 — Head Node is Duplicate

$ Input: head = [1,1,2,3]

› Output: [2,3]

💡 Note: The head node value 1 is duplicated, so both 1's are removed. Only 2 and 3 remain.

Example 3 — All Elements are Duplicates

$ Input: head = [1,1,2,2]

› Output: []

💡 Note: Every value appears exactly twice, so all nodes are removed, resulting in an empty list.

Constraints

The number of nodes in the list is in the range [0, 300]
-100 ≤ Node.val ≤ 100
The list is guaranteed to be sorted in ascending order

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted linked list [1,2,3,3,4,4,5] with some duplicate values

Process

Identify and remove ALL nodes that have duplicate values (3,3 and 4,4)

Output

Resulting list [1,2,5] contains only unique values

Key Takeaway

🎯 Key Insight: Use a dummy node to handle edge cases and skip entire duplicate sequences in one pass

Asked in

M Microsoft 45 a Amazon 38 G Google 32 f Facebook 28

The key insight is to use a dummy node to simplify edge cases and detect duplicate sequences in one pass. The optimal approach uses two pointers: when duplicates are found, skip the entire sequence and link around it. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two-Pass Count and Rebuild	O(n)	O(n)	First pass counts frequencies, second pass rebuilds list with unique values only
One-Pass with Dummy Head	O(n)	O(1)	Use dummy node and two pointers to handle duplicates in single pass

Two-Pass Count and Rebuild — Algorithm Steps

Step 1: Traverse list and count frequency of each value
Step 2: Traverse list again and keep only nodes with frequency 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

First pass counts how many times each value appears

Filter Unique

Second pass keeps only values with count = 1

Build Result

Create new list with unique values only

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* solution(struct ListNode* head) {
    if (!head) return NULL;
    
    // Count frequencies (simple approach for small ranges)
    int freq[201] = {0}; // Assuming values in range [-100, 100]
    struct ListNode* current = head;
    while (current) {
        freq[current->val + 100]++; // Offset by 100 for negative values
        current = current->next;
    }
    
    // Build new list with unique values only
    struct ListNode dummy = {0, NULL};
    struct ListNode* tail = &dummy;
    current = head;
    
    while (current) {
        if (freq[current->val + 100] == 1) {
            struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
            newNode->val = current->val;
            newNode->next = NULL;
            tail->next = newNode;
            tail = tail->next;
        }
        current = current->next;
    }
    
    return dummy.next;
}

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        current = current->next;
        current->val = arr[i];
        current->next = NULL;
    }
    return head;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int arr[100];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    struct ListNode* head = arrayToList(arr, size);
    struct ListNode* result = solution(head);
    
    printf("[");
    int first = 1;
    while (result) {
        if (!first) printf(",");
        printf("%d", result->val);
        first = 0;
        result = result->next;
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through the linked list of n nodes

✓ Linear Growth

Space Complexity

O(n)

Hash map stores frequency count for each unique value

⚡ Linearithmic Space

187.5K Views

Medium-High Frequency

~25 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two-Pass Count and Rebuild — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler