Remove Duplicates from Sorted List - Practice Coding Problems

Remove Duplicates from Sorted List - Problem

Linked List Easy

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

The linked list is sorted in ascending order.

Input & Output

Example 1 — Basic Duplicates

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

› Output: [1,2]

💡 Note: The linked list has duplicate 1s. After removing duplicates, we get [1,2] with each element appearing only once.

Example 2 — Multiple Groups

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

› Output: [1,2,3]

💡 Note: We have two groups of duplicates: two 1s and two 3s. Remove one from each group to get [1,2,3].

Example 3 — No Duplicates

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

› Output: [1,2,3]

💡 Note: The list has no duplicates, so it remains unchanged.

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 with duplicates: [1,1,2,3,3]

Process

Compare adjacent nodes and skip duplicates

Output

List with unique values: [1,2,3]

Key Takeaway

🎯 Key Insight: In sorted lists, duplicates are always adjacent, enabling single-pass removal

Asked in

F Facebook 32 a Amazon 28 M Microsoft 24 G Google 19

The key insight is that in a sorted linked list, duplicate values are always adjacent. We can solve this in one pass by comparing each node with its next node. Best approach is single traversal with adjacent comparison. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Traversal	O(n)	O(1)	Walk through once, compare adjacent nodes and remove duplicates
Nested Loop Comparison	O(n²)	O(1)	For each node, check all remaining nodes to remove duplicates

Single Pass Traversal — Algorithm Steps

Start from head node
Compare current node with next node
If values match, skip the next node
Continue until end of list

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Adjacent

Check if current equals next node

Skip Duplicate

Update pointer to bypass duplicate

Continue

Move to next unique node

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 head;
    
    struct ListNode* current = head;
    while (current->next) {
        if (current->val == current->next->val) {
            struct ListNode* temp = current->next;
            current->next = current->next->next;
            free(temp);
        } else {
            current = current->next;
        }
    }
    
    return head;
}

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

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

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int arr[100];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        arr[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    struct ListNode* head = arrayToList(arr, size);
    struct ListNode* result = solution(head);
    printList(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the linked list, visiting each node exactly once

✓ Linear Growth

Space Complexity

O(1)

Only using a few pointer variables, no extra data structures needed

✓ Linear Space

125.0K Views

High Frequency

~15 min Avg. Time

3.6K 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

Single Pass Traversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler