algoadvance

Leetcode 82. 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.

Example:

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

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

Clarifying Questions

  1. Q: Can the list be empty?
    A: Yes, the list can be empty, and if so the function should return nullptr.

  2. Q: Are the elements in the linked list always sorted?
    A: Yes, it is guaranteed that the linked list is sorted.

  3. Q: How should I handle cases where all elements are duplicates?
    A: If all elements are duplicates, the function should return an empty list (nullptr).

  4. Q: Is extra space allowed?
    A: The goal is to solve the problem with O(1) additional space, excluding space for the output list.

Strategy

  1. Initialization: Use a dummy head node that helps in handling edge cases such as when the first few nodes are duplicates.
  2. Iterate: Traverse the linked list to check for duplicates.
  3. Skip Duplicates: If a duplicate is found, skip all nodes with that value.
  4. Link Nodes: Correctly link the previous node to the next distinct node.
  5. Return: Return the modified list starting from the dummy head’s next node.

We will keep track using pointers (Current, Prev) to facilitate linking.

Code

#include <iostream>

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) return nullptr;

        // Dummy node
        ListNode* dummy = new ListNode(0, head);
        ListNode* prev = dummy;

        while (head && head->next) {
            if (head->val == head->next->val) {
                // Skip all nodes with the current value
                int dup_val = head->val;
                while (head && head->val == dup_val) {
                    head = head->next;
                }
                prev->next = head;  // Link prev to the first node after duplicates
            } else {
                // Move prev to current node as it's unique upto now
                prev = prev->next;
                head = head->next;
            }
        }

        return dummy->next;
    }
};

// Utility function to create a linked list from an array
ListNode* createList(const std::vector<int>& values) {
    ListNode* head = new ListNode(values[0]);
    ListNode* current = head;
    for (int i = 1; i < values.size(); ++i) {
        current->next = new ListNode(values[i]);
        current = current->next;
    }
    return head;
}

// Utility function to print a linked list
void printList(ListNode* head) {
    while (head != nullptr) {
        std::cout << head->val;
        if (head->next) std::cout << " -> ";
        head = head->next;
    }
    std::cout << std::endl;
}

// Example usage
int main() {
    std::vector<int> values = {1, 2, 3, 3, 4, 4, 5};
    ListNode* head = createList(values);
    Solution solution;
    ListNode* result = solution.deleteDuplicates(head);
    printList(result);  // Output should be 1 -> 2 -> 5
    return 0;
}

Time Complexity and Space Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list. Each node is processed at most twice (once for checking duplicates and once for linking).

Space Complexity: O(1), since we are not using any extra space that grows with the input size (excluding the output size).

Feel free to ask if you have any further questions!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI