Remove Duplicates From an Unsorted Linked List

Remove Duplicates From an Unsorted Linked List - Problem

Given the head of a linked list, find all the values that appear more than once in the list and delete the nodes that have any of those values.

Return the linked list after the deletions.

Note: A value that appears multiple times should have all its occurrences removed from the list.

Input & Output

Example 1 — Basic Case

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

› Output: [1,3]

💡 Note: Value 2 appears twice, so remove all nodes with value 2. Keep nodes with values 1 and 3 that appear only once.

Example 2 — Multiple Duplicates

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

› Output: []

💡 Note: Both values 1 and 2 appear twice, so all nodes are removed. The result is an empty list.

Example 3 — No Duplicates

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

› Output: [1,2,3]

💡 Note: All values appear exactly once, so no nodes are removed. The original list is returned.

Constraints

The number of nodes in the given list is in the range [1, 10⁵]
1 ≤ Node.val ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list with some duplicate values

Process

Identify values that appear more than once

Output

Remove ALL nodes with duplicate values

Key Takeaway

🎯 Key Insight: Use frequency counting to identify duplicates, then remove ALL occurrences of duplicate values

Asked in

M Microsoft 25 a Amazon 20 G Google 15

The key insight is to use a two-pass approach: first count the frequency of each value, then remove all nodes whose values appear more than once. Best approach is Two-Pass Hash Map with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	For each node, traverse entire list to count occurrences, then remove if count > 1
Two-Pass Hash Map	O(n)	O(n)	First pass counts frequencies, second pass removes nodes with frequency > 1

Brute Force — Algorithm Steps

For each node, count occurrences by traversing entire list
If count > 1, mark value for removal
Remove all nodes with marked values

Visualization

Tap to expand

Step-by-Step Walkthrough

Check First Node

Count how many times value 1 appears

Check Each Node

For each node, scan entire list

Remove Duplicates

Remove all nodes with count > 1

Code -

solution.c — C

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

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

struct ListNode* solution(struct ListNode* head) {
    if (!head) return NULL;
    
    // Find all values that appear more than once
    int duplicates[10001] = {0}; // Assuming values in range [-5000, 5000]
    bool hasDuplicates[10001] = {false};
    
    struct ListNode* current = head;
    while (current) {
        int count = 0;
        struct ListNode* temp = head;
        while (temp) {
            if (temp->val == current->val) {
                count++;
            }
            temp = temp->next;
        }
        if (count > 1) {
            hasDuplicates[current->val + 5000] = true;
        }
        current = current->next;
    }
    
    // Remove all nodes with duplicate values
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = head;
    struct ListNode* prev = dummy;
    current = head;
    
    while (current) {
        if (hasDuplicates[current->val + 5000]) {
            prev->next = current->next;
        } else {
            prev = current;
        }
        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->next->val = arr[i];
        current->next->next = NULL;
        current = current->next;
    }
    return head;
}

void printList(struct ListNode* head) {
    printf("[");
    struct ListNode* current = head;
    bool first = true;
    while (current) {
        if (!first) printf(",");
        printf("%d", current->val);
        first = false;
        current = current->next;
    }
    printf("]\n");
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[1000];
    int size = 0;
    char* ptr = line + 1; // Skip '['
    while (*ptr && *ptr != ']') {
        if (*ptr >= '0' && *ptr <= '9' || *ptr == '-') {
            arr[size++] = atoi(ptr);
            while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
        } else {
            ptr++;
        }
    }
    
    struct ListNode* head = arrayToList(arr, size);
    struct ListNode* result = solution(head);
    printList(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each of n nodes, we traverse the list (O(n)) to count occurrences, then traverse again (O(n)) to remove

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 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

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler