Problem Statement

We are given a singly linked list that is sorted in non-decreasing order. We have to remove all duplicates such that each element appears only once in the linked list.

Examples

Example 1:

Input: 1 -> 1 -> 2 -> 3 -> 3 -> 4 -> 5 -> 5 -> nullptr
Output: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr

Approaches

1️⃣ Traversing

Intuition:

Since the linked list is sorted, duplicates will always be next to each other. We can use a simple traversal to check if the current node's value is the same as the next node's value. If it is, we remove the next node by adjusting the next pointer of the current node.

Code:

#include <iostream>

struct ListNode {
    int data;
    ListNode* next;
    ListNode(int x) : data(x), next(nullptr) {}
};

// Function to remove duplicates from a sorted linked list
ListNode* removeDuplicates(ListNode* head) {
    ListNode* current = head;

    // Traverse the list
    while (current != nullptr && current->next != nullptr) {
        // Check for duplicate nodes
        if (current->data == current->next->data) {
            ListNode* duplicateNode = current->next; // Node to be deleted
            current->next = current->next->next;     // Bypass the duplicate node
            delete duplicateNode;                   // Free memory of the duplicate node
        } else {
            // Move to the next distinct element
            current = current->next;
        }
    }

    return head;
}

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

int main() {
    // Create a sorted linked list with duplicates
    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);
    head->next->next->next->next->next = new ListNode(4);
    head->next->next->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next->next->next = new ListNode(5);

    std::cout << "Original list: ";
    printList(head);

    // Remove duplicates from the sorted linked list
    head = removeDuplicates(head);

    std::cout << "List after removing duplicates: ";
    printList(head);

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n)
  • The algorithm traverses the linked list once. Each operation within the loop (comparison and possible deletion) takes constant time, resulting in a linear time complexity relative to the number of nodes (n) in the list.
• Space Complexity: O(1)
  • The solution uses a constant amount of extra space for pointers (current), so the space complexity is constant.