Remove duplicates from a sorted doubly linked list | GFG Practice | Optimal Solution

Given the head of a sorted doubly linked list, remove all duplicate nodes from the list. Each node should appear only once in the final list.

Here’s the [Problem Link] to begin with.

Example 1:

Input:
n = 6
1<->1<->1<->2<->3<->4
Output:
1<->2<->3<->4
Explanation:
Only the first occurance of node with value 1 is 
retained, rest nodes with value = 1 are deleted.

Example 2:

Input:
n = 7
1<->2<->2<->3<->3<->4<->4
Output:
1<->2<->3<->4
Explanation:
Only the first occurance of nodes with values 2,3 and 4 are 
retained, rest repeating nodes are deleted.

Your Task:
You have to complete the method removeDuplicates() which takes 1 argument: the head of the linked list.  Your function should return a pointer to a linked list with no duplicate element.

Constraint:
1 <= n <= 10⁵
Expected Time Complexity: O(n)
Expected Space Complexity: O(1)

Solution: Optimal Approach (Single Pass Traversal)

Intuition

Think of this like organizing a bookshelf where books are arranged alphabetically, but you have multiple copies of some books! Since the books are already sorted, all duplicate copies will be sitting right next to each other. You can simply walk through the shelf and whenever you see two identical books next to each other, remove one of them. In a doubly linked list, we do the same – traverse the list and remove duplicate nodes that are adjacent to each other.

Detailed Approach

1. Start Traversal: Begin from the head and traverse through each node
2. Check for Duplicates: For each node, check if its data matches the previous node’s data
3. Remove Duplicate: When a duplicate is found, remove the current node by updating the links
4. Update Links: Properly connect the previous and next nodes to skip the duplicate
5. Handle Head Update: If the head node itself is a duplicate, update the head pointer
6. Continue: Move to the next node and repeat until the end

Code

class Solution:
    #Function to remove duplicates from sorted doubly linked list.
    def removeDuplicates(self, head):
        cur = head  # Current node pointer for traversal
        
        while cur:
            # Check if current node is duplicate of previous node
            if cur.prev and cur.prev.data == cur.data:
                # Handle case where previous node is the head
                if cur.prev == head:
                    cur.prev = None        # Remove backward link
                    head = cur            # Update head to current node
                else:
                    # Remove the previous duplicate node by updating links
                    cur.prev.prev.next = cur     # Connect prev's prev to current
                    cur.prev = cur.prev.prev     # Connect current to prev's prev
            
            cur = cur.next  # Move to next node
        
        return head

Code Explanation

This solution traverses the doubly linked list and removes duplicate nodes by updating the forward and backward links. When a duplicate is detected (current node’s data equals previous node’s data), it removes the previous node by reconnecting the links. The algorithm handles the special case where the head node itself is part of a duplicate pair. However, there’s an important note: this implementation removes the previous node when a duplicate is found, rather than the more typical approach of removing the current node.

Dry Run

Let’s trace through: 1 <-> 1 <-> 2 <-> 3 <-> 3

Initial Setup:

• cur = 1 (first node), head = 1

Step 1:

• cur.prev = None, so no duplicate check
• cur = 1 (second node)

Step 2:

• cur.prev.data = 1, cur.data = 1 (duplicate found!)
• cur.prev == head, so update head = cur (second 1)
• cur.prev = None
• cur = 2

Step 3:

• cur.prev.data = 1, cur.data = 2 (no duplicate)
• cur = 3 (first occurrence)

Step 4:

• cur.prev.data = 2, cur.data = 3 (no duplicate)
• cur = 3 (second occurrence)

Step 5:

• cur.prev.data = 3, cur.data = 3 (duplicate found!)
• cur.prev != head, so update links
• Connect 2 directly to second 3, remove first 3
• cur = None

Result: 1 <-> 2 <-> 3

Time and Space Complexity

• Time Complexity: O(n) – We traverse the list once, visiting each node exactly once
• Space Complexity: O(1) – We only use a few pointer variables, no extra space needed

Simplifying It

This approach is like walking through a line of people and whenever you find two people with the same name standing next to each other, you ask the first person to leave. Since everyone is already arranged in alphabetical order by name, all people with the same name will be standing together, making it easy to spot and remove duplicates.

Alternative Approach (More Common Implementation)

While the provided solution works, a more intuitive approach would be to remove the current node when a duplicate is found:

# Alternative approach (more common)
def removeDuplicates(self, head):
    cur = head
    while cur and cur.next:
        if cur.data == cur.next.data:
            # Remove cur.next node
            duplicate = cur.next
            cur.next = duplicate.next
            if duplicate.next:
                duplicate.next.prev = cur
        else:
            cur = cur.next
    return head

This approach is often more intuitive because it removes the “next” duplicate rather than the “previous” one.

Summary

This optimal solution efficiently removes all duplicates in a single pass through the sorted doubly linked list. The key insight is that in a sorted list, all duplicate elements will be adjacent, so we only need to check neighboring nodes.

The main challenge in doubly linked list problems is properly managing both forward and backward pointers when updating links. This problem demonstrates important concepts like link manipulation and edge case handling (such as updating the head pointer when necessary).

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.