Remove Duplicate Elements from a Sorted Linked List in C++

This C++ program demonstrates how to remove duplicate elements from a sorted linked list. It uses a simple approach of traversing the list and deleting consecutive duplicate nodes.

Program Code

#include <iostream>

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

// Function to remove duplicates from a sorted linked list
void removeDuplicates(ListNode* head) {
    ListNode* current = head;
    while (current != NULL && current->next != NULL) {
        if (current->val == current->next->val) {
            ListNode* nextNode = current->next;
            current->next = nextNode->next;
            delete nextNode;  // Free memory of the duplicate node
        } else {
            current = current->next;  // Move to next node
        }
    }
}

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

int main() {
    // Create a sorted linked list with duplicates: 1->1->2->3->3
    ListNode* a = new ListNode(1);
    a->next = new ListNode(1);
    a->next->next = new ListNode(2);
    a->next->next->next = new ListNode(3);
    a->next->next->next->next = new ListNode(3);

    std::cout << "Original List: ";
    printList(a);

    removeDuplicates(a);

    std::cout << "List After Removing Duplicates: ";
    printList(a);

    return 0;
}

Explanation of the Code

The program includes a struct definition for the linked list node, each containing an integer value and a pointer to the next node. The removeDuplicates() function is designed to work on a sorted linked list and removes duplicate nodes by adjusting the pointers of the nodes that have unique values to skip the duplicate nodes.

This method involves checking each node’s value against its successor’s value and skipping over any duplicates by changing the current node’s next pointer. This also involves proper memory management where the duplicate nodes are deleted to free up memory.

Conclusion

This C++ program is an effective solution for removing duplicates from a sorted linked list. It ensures efficient memory usage by deleting duplicate nodes and maintains the original list’s order with minimal pointer adjustments.