Remove Duplicates from a Sorted Doubly Linked List

87.2k
0

Given the head of a sorted doubly linked list, remove duplicate nodes so every value appears exactly once and return the head of the modified list.

Each node stores an integer value, a next pointer, and a previous pointer. The final doubly linked list must remain sorted, and every previous pointer must correctly point to the preceding node.

Example 1

Input: head = [1, 1, 2, 2, 3, 4, 4]

Output: [1, 2, 3, 4]

Explanation: Consecutive equal values are reduced to a single occurrence.

Example 2

Input: head = [5, 5, 5, 5]

Output: [5]

Explanation: All nodes store the same value, so only one node remains.

Brute Force Approach

A sorted doubly linked list groups equal values in adjacent positions. A simple baseline collects the first value from every equal-value group and creates a fresh doubly linked list from the collected unique values.

The method avoids delicate deletion cases and keeps the sorted order automatically, but extra storage and fresh node allocation make the method less memory efficient.

Algorithm

  • Return NULL when head is NULL, as there are no nodes to process or values to keep.

  • Initialize an empty array for unique values, as storing one value from each group makes it easy to build the result without modifying the original list.

  • Traverse the sorted list and append the current value to the array, since the first value of each group represents a distinct value.

  • Skip all remaining nodes with the same value, as the sorted order guarantees that duplicates of the current value appear consecutively.

  • Continue until the entire list has been processed, ensuring that each distinct value is stored exactly once and the original sorted order is preserved.

  • Create a new doubly linked list from the collected values, as every unique value now needs a corresponding node in the result.

  • Return the head of the newly created list, since it represents the sorted doubly linked list without duplicate values.

Dry Run

remove duplicate

remove duplicate

Solution

#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
Node* prev;
// Constructor for a doubly linked list node.
Node(int value) {
data = value;
next = nullptr;
prev = nullptr;
}
};
class Solution {
public:
// Removes duplicate values from a sorted doubly linked list.
Node* removeDuplicates(Node* head) {
if (head == nullptr) {
return nullptr;
}
vector<int> values;
Node* current = head;
// Store one value from each group of equal nodes.
while (current != nullptr) {
values.push_back(current->data);
int duplicateValue = current->data;
// Skip all nodes having the same value.
while (current != nullptr &&
current->data == duplicateValue) {
current = current->next;
}
}
// Create the first node of the new list.
Node* newHead = new Node(values[0]);
Node* tail = newHead;
// Build a new doubly linked list using unique values.
for (int index = 1; index < (int)values.size(); index++) {
Node* node = new Node(values[index]);
tail->next = node;
node->prev = tail;
tail = node;
}
return newHead;
}
};
// Creates a doubly linked list from the given array.
Node* createList(vector<int>& arr) {
if (arr.empty()) {
return nullptr;
}
Node* head = new Node(arr[0]);
Node* tail = head;
for (int index = 1; index < (int)arr.size(); index++) {
Node* node = new Node(arr[index]);
tail->next = node;
node->prev = tail;
tail = node;
}
return head;
}
// Prints the doubly linked list from head to tail.
void printList(Node* head) {
Node* current = head;
while (current != nullptr) {
cout << current->data;
if (current->next != nullptr) {
cout << " ";
}
current = current->next;
}
}
// Driver code.
int main() {
vector<int> arr = {1, 1, 2, 2, 3, 4, 4};
Node* head = createList(arr);
Solution sol;
head = sol.removeDuplicates(head);
printList(head);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the total number of nodes in the original doubly linked list. Every node is visited once, followed by reconstruction of the unique-value list.

Space Complexity: O(N), where N is the total number of nodes; the array and newly created list can require linear extra space.

Optimal Approach

The sorted order places duplicate values next to each other. A single traversal can compare every node with the next node and delete the next node whenever both values match.

The current node should remain fixed after deleting a duplicate, because more duplicates of the same value may still follow immediately after the updated next pointer.

Algorithm

  • Initialize current with head, as the traversal needs to compare each node with its immediate next node.

  • Traverse while current and current->next both exist, since a comparison is possible only when an adjacent pair is available.

  • Compare the values of current and current->next, as equal adjacent values indicate that the next node is a duplicate in the sorted list.

  • When both values match, store the duplicate node and connect current->next to duplicate->next, which bypasses the duplicate node from the forward links.

  • Update duplicate->next->prev to current when duplicate->next exists, so the backward links remain consistent after the deletion.

  • Keep current at the same node after deleting a duplicate, as more nodes with the same value may immediately follow and need to be checked.

  • Move current to current->next only when the adjacent values are different, since the current node has no duplicate immediately after it.

  • Return the original head after traversal ends, as the head remains unchanged and all consecutive duplicate nodes have been removed.

Dry Run

remove duplicate (3)

remove duplicate (3)

Solution

#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
Node* prev;
// Constructor for a doubly linked list node.
Node(int value) {
data = value;
next = nullptr;
prev = nullptr;
}
};
class Solution {
public:
// Removes duplicate values from a sorted doubly linked list.
Node* removeDuplicates(Node* head) {
Node* current = head;
// Compare each node with its next adjacent node.
while (current != nullptr && current->next != nullptr) {
if (current->data == current->next->data) {
Node* duplicate = current->next;
// Remove the duplicate node from the forward link.
current->next = duplicate->next;
// Update the backward link of the next node.
if (duplicate->next != nullptr) {
duplicate->next->prev = current;
}
delete duplicate;
} else {
// Move forward when adjacent values are different.
current = current->next;
}
}
return head;
}
};
// Creates a doubly linked list from the given array.
Node* createList(vector<int>& arr) {
if (arr.empty()) {
return nullptr;
}
Node* head = new Node(arr[0]);
Node* tail = head;
for (int index = 1; index < (int)arr.size(); index++) {
Node* node = new Node(arr[index]);
tail->next = node;
node->prev = tail;
tail = node;
}
return head;
}
// Prints the doubly linked list from head to tail.
void printList(Node* head) {
Node* current = head;
while (current != nullptr) {
cout << current->data;
if (current->next != nullptr) {
cout << " ";
}
current = current->next;
}
}
// Driver code.
int main() {
vector<int> arr = {1, 1, 2, 2, 3, 4, 4};
Node* head = createList(arr);
Solution sol;
head = sol.removeDuplicates(head);
printList(head);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the total number of nodes in the doubly linked list. Every node is visited or deleted at most once.

Space Complexity: O(1), as only a constant number of pointer variables are used apart from the input list.

Interview follow-up Questions

Yes. Sorted order places equal values adjacent to each other, so a single left-to-right traversal is enough.

Linked List

Read Similar Blogs

Linked List

Swap Nodes in Pairs

Given the head of a singly linked list, swap every two adjacent nodes and return the modified head. Node values must stay inside the original nodes, so the task swaps node links instead of rewritin...

59.9k
Linked List

Merge Two Sorted Linked Lists

Given heads of two sorted linked lists, merge both lists into one sorted linked list and return the head of the merged list. Every node stores an integer value and a pointer to the next node. The f...

114.6k
Linked List

Find pairs with given sum in Doubly Linked List

Given a sorted doubly linked list containing positive distinct integers and an integer target, find every pair of node values whose sum equals target. Return pairs in increasing order based on the...

101.5k
Comments0