Problem Statement

Given the head of a doubly linked list with its values sorted in non-decreasing order. Remove all duplicate occurrences of any value in the list so that only distinct values are present in the list.

Return the head of the modified linked list.

Examples

Example 1:

Input: head -> 1 <-> 1 <-> 3 <-> 3 <-> 4 <-> 5
Output: head -> 1 <-> 3 <-> 4 <-> 5

Explanation: head -> 1 <-> 1 <-> 3 <-> 3 <-> 4 <-> 5
The underlined nodes were deleted to get the desired result.

Example 2:

Input: head -> 1 <-> 1 <-> 1 <-> 1 <-> 1 <-> 2
Output: head -> 1 <-> 2

Explanation: head -> 1 <-> 1 <-> 1 <-> 1 <-> 1 <-> 2
The underlined nodes were deleted to get the desired result.

Different Approaches

1️⃣ Traversal

Intuition:

Since the list is sorted, any duplicates will always occur contiguously. This allows us to traverse the list once and remove consecutive nodes with the same value. By updating the pointers of the previous and next nodes appropriately, we can ensure the list remains properly linked while removing duplicates.

Approach:

1. Start by setting a temporary pointer to the head of the doubly linked list. This pointer will be used to traverse the list.
2. Loop through the list until the end is reached. For each node, check if its next node has the same value.
3. Remove Duplicate Nodes:
   1. If the next node has the same value as the current node:
      1. Continue moving to the next node until a node with a different value is found.
      2. Delete all duplicate nodes encountered.
      3. Link the current node to the next non-duplicate node.
      4. Update the previous pointer of the next non-duplicate node (if it exists).
   2. Move the temporary pointer to the next node and repeat the process.
4. After the traversal, return the updated head of the list.

Code:

#include <bits/stdc++.h>

using namespace std;

// Definition of Single Linked List
struct ListNode {
    int val;
    ListNode* next;
    ListNode* prev;
    ListNode() {
        val = 0;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1) {
        val = data1;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1, ListNode* next1, ListNode* prev1) {
        val = data1;
        next = next1;
        prev = prev1;
    }
};

class Solution {
public:
    // To remove duplicates from a sorted doubly linked list
    ListNode* removeDuplicates(ListNode* head) {
        ListNode* temp = head;
        
        // Traverse the list
        while (temp != NULL && temp->next != NULL) {
            ListNode* nextNode = temp->next;
            
            // Remove all duplicate nodes
            while (nextNode != NULL && nextNode->val == temp->val) {
                // Store the duplicate node
                ListNode* duplicate = nextNode;
                // Move to the next node
                nextNode = nextNode->next;
                // Delete the duplicate node
                delete duplicate;
            }
            
           /* Link the current node 
           to the next non-duplicate node*/
            temp->next = nextNode;
            /*Update previous pointer 
            of next non-duplicate node*/
            if (nextNode != NULL) {
                nextNode->prev = temp;
            }
            
            // Move to the next node
            temp = temp->next;
        }
        
        return head;
    }
};

// Function to print doubly linked list
void printList(ListNode* head) {
    ListNode* temp = head;
    while (temp != NULL) {
        cout << temp->val << " ";
        temp = temp->next;
    }
    cout << endl;
}

// Helper function to create a new node
ListNode* newNode(int data) {
    ListNode* node = new ListNode(data);
    return node;
}

int main() {
    // Creating a sorted doubly linked list:
    ListNode* head = newNode(1);
    head->next = newNode(2);
    head->next->prev = head;
    head->next->next = newNode(2);
    head->next->next->prev = head->next;
    head->next->next->next = newNode(3);
    head->next->next->next->prev = head->next->next;
    head->next->next->next->next = newNode(4);
    head->next->next->next->next->prev = head->next->next->next;
    head->next->next->next->next->next = newNode(4);
    head->next->next->next->next->next->prev = head->next->next->next->next;
    head->next->next->next->next->next->next = newNode(5);
    head->next->next->next->next->next->next->prev = head->next->next->next->next->next;

    // Print original list
    cout << "Original list: ";
    printList(head);

    // Remove duplicates
    Solution sol;
    head = sol.removeDuplicates(head);

    // Print modified list
    cout << "Modified list: ";
    printList(head);

    return 0;
}

Complexity Analysis:

• Time Complexity:O(n) and not O(n^2) because each node in the doubly linked list is visited exactly once. The outer loop traverses each distinct node, and the inner loop skips over consecutive duplicates in a single pass, ensuring a total linear traversal of the list. Thus the combined process does not create nested iterations and remains efficient.
• Space Complexity:O(1) no extra space is used.