algoadvance

Leetcode 83. Remove Duplicates from Sorted List

Problem Statement

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.

Example:

Input:

1 -> 1 -> 2

Output:

1 -> 2

Input:

1 -> 1 -> 2 -> 3 -> 3

Output:

1 -> 2 -> 3

Clarifying Questions

  1. Q: What is the range of values for the nodes in the list? A: The values in the list are within the integer limits.

  2. Q: Can the linked list be empty? A: Yes, the linked list can be empty.

  3. Q: What should we return if the linked list is empty? A: If the linked list is empty, we should return nullptr.

  4. Q: Will the linked list always be sorted? A: Yes, the linked list will always be sorted.

Strategy

The problem requires us to remove duplicate elements from a sorted linked list such that each element appears only once. We need to traverse the linked list and compare each node with the next node. If they are the same, we will skip the next node. If they are different, we move to the next node.

Steps:

  1. Traverse the linked list starting from the head.
  2. For each node, check if its value is the same as the next node’s value.
  3. If it is, skip the next node by changing the current node’s next pointer.
  4. If it’s not, move the current node to the next node.
  5. Continue until the end of the list is reached.

Code

#include <iostream>

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) {
        // Edge case: if the list is empty
        if (head == nullptr) {
            return nullptr;
        }
        
        ListNode* current = head;
        
        while (current != nullptr && current->next != nullptr) {
            if (current->val == current->next->val) {
                // Skip the next node as it is a duplicate
                ListNode* temp = current->next;
                current->next = current->next->next;
                delete temp; // Free the memory of the duplicate node
            } else {
                // Move to the next node
                current = current->next;
            }
        }

        return head;
    }
};

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

// Example usage
int main() {
    // Creating a linked list: 1 -> 1 -> 2 -> 3 -> 3
    ListNode* head = new ListNode(1);
    head->next = new ListNode(1);
    head->next->next = new ListNode(2);
    head->next->next->next = new ListNode(3);
    head->next->next->next->next = new ListNode(3);

    Solution solution;
    ListNode* result = solution.deleteDuplicates(head);

    printList(result); // Output should be: 1 2 3

    // Free the allocated memory for the linked list nodes
    while (result != nullptr) {
        ListNode* temp = result;
        result = result->next;
        delete temp;
    }

    return 0;
}

Time Complexity

The time complexity of the provided solution is O(n), where n is the number of nodes in the linked list. This is because we traverse the entire list once to process all the nodes.

The space complexity is O(1) since we are using a constant amount of extra space for the pointers (current and temp).

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