Remove Duplicates from Sorted List - CPP Solution

1. Introduction

This blog post addresses a common problem in linked list manipulation: removing duplicates from a sorted linked list. The challenge is to delete all duplicates such that each element appears only once, ensuring that the list remains sorted.

Problem

Given the head of a sorted linked list, the task is to delete all duplicates, allowing each element to appear only once, and return the modified list.

2. Solution Steps

1. Initialize a pointer current to traverse the list.

2. While traversing, compare the current node with the next node.

3. If a duplicate is found, delete the duplicate and update the next pointer of the current node.

4. Continue this process until the end of the list.

5. Return the modified list without duplicates.

3. Code Program

#include <iostream>
using namespace std;

// Define the ListNode structure
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

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

    while (current && current->next) {
        if (current->val == current->next->val) {
            ListNode *temp = current->next;
            current->next = current->next->next;
            delete temp;
        } else {
            current = current->next;
        }
    }

    return head;
}

// Function to print the linked list
void printLinkedList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "nullptr\n";
}

int main() {
    // Creating 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 = deleteDuplicates(head);
    printLinkedList(head); // Expected output: 1 -> 2 -> 3 -> nullptr
    return 0;
}

Output:

1 -> 2 -> 3 -> nullptr

Explanation:

The deleteDuplicates function iteratively examines each node of the list and compares it with the next node. If a duplicate is found, it deletes the duplicate node and updates the next pointer of the current node to bypass the deleted node. This process is repeated until all duplicates are removed. The function returns the head of the modified list, which is free of duplicates and remains sorted.