Remove duplicated from sorted DLL

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

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

Dry Run

Solution

#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;
}
import java.util.*;

// Definition of doubly linked list
class 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 {
    // To remove duplicates from a sorted doubly linked list
    public 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
                duplicate = null;
            }

            /* 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
public class Main {
    public static void printList(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
        System.out.println();
    }

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

    public static void main(String[] args) {
        // 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
        System.out.print("Original list: ");
        printList(head);

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

        // Print modified list
        System.out.print("Modified list: ");
        printList(head);
    }
}
# Definition of doubly linked list
class ListNode:
    def __init__(self, val=0, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev

class Solution:
    # To remove duplicates from a sorted doubly linked list
    def removeDuplicates(self, head):
        temp = head
        
        # Traverse the list
        while temp is not None and temp.next is not None:
            nextNode = temp.next
            
            # Remove all duplicate nodes
            while nextNode is not None and nextNode.val == temp.val:
                # Store the duplicate node
                duplicate = nextNode
                # Move to the next node
                nextNode = nextNode.next
                # Delete the duplicate node
                del duplicate
            
            # Link the current node to the next non-duplicate node
            temp.next = nextNode
            # Update previous pointer of next non-duplicate node
            if nextNode is not None:
                nextNode.prev = temp
            
            # Move to the next node
            temp = temp.next
        
        return head

# Function to print doubly linked list
def printList(head):
    temp = head
    while temp is not None:
        print(temp.val, end=" ")
        temp = temp.next
    print()

# Helper function to create a new node
def newNode(data):
    return ListNode(data)

if __name__ == "__main__":
    # Creating a sorted doubly linked list:
    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
    print("Original list: ", end="")
    printList(head)

    # Remove duplicates
    sol = Solution()
    head = sol.removeDuplicates(head)

    # Print modified list
    print("Modified list: ", end="")
    printList(head)
// Definition of doubly linked list
class ListNode {
    constructor(val = 0, next = null, prev = null) {
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}

class Solution {
    // To remove duplicates from a sorted doubly linked list
    removeDuplicates(head) {
        let temp = head;
        
        // Traverse the list
        while (temp !== null && temp.next !== null) {
            let nextNode = temp.next;
            
            // Remove all duplicate nodes
            while (nextNode !== null && nextNode.val === temp.val) {
                // Store the duplicate node
                let duplicate = nextNode;
                // Move to the next node
                nextNode = nextNode.next;
                // Delete the duplicate node
                duplicate = null;
            }
            
            /* 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
function printList(head) {
    let temp = head;
    while (temp !== null) {
        process.stdout.write(temp.val + " ");
        temp = temp.next;
    }
    console.log();
}

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

(function() {
    // Creating a sorted doubly linked list:
    let 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
    process.stdout.write("Original list: ");
    printList(head);

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

    // Print modified list
    process.stdout.write("Modified list: ");
    printList(head);
})();

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.

Problem List

Remove duplicated from sorted DLL

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code