Problem 2: Remove Duplicates from Sorted List (easy)

Problem Statement:

Given a sorted linked list, remove all the duplicate elements to leave only distinct numbers. The linked list should remain sorted, and the modified list should be returned.

Examples

Example 1:

Input: 1 -> 1 -> 2
Output: 1 -> 2
Justification: Since 1 is repeated, we remove the duplicate to leave a sorted list of unique numbers.

Example 2:

Input: 1 -> 2 -> 2 -> 3
Output: 1 -> 2 -> 3
Justification: Here, 2 is the duplicate element, and by removing it, we obtain a list containing only distinct elements.

.....

Like the course? Get enrolled and start learning!

Divyanshu Varma

· a year ago

/*
 * We should delete unused bypassed nodes otherwise
 * if you had n nodes to begin with and deleted m nodes 
 * you will still be consuming n nodes worth of memory. 
 */
 
ListNode* deleteDuplicates(ListNode* head) {
        if(!head or !head->next) { // base case
            return head;
        }

        auto curr = head, ahead = head->next; // adjacent nodes
        while(ahead) {
            if(curr->val == ahead->val) {
                auto temp = ahead;
                curr->next = ahead->next; // skip duplicate
                ahead = ahead->next;
                delete temp; // delete unused node
            } else {
                curr = curr->next;
                ahead = ahead->next;
            }
        }

        return head;
    }