Remove Duplicates from Sorted List II

82.Remove Duplicates from Sorted List II

Linked List

Two Pointers

Problem Statement:

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example:

Input:

head = [1→2→3→3→4→4→5]

→

Output:

[1→2→5]

3 and 4 appear multiple times, so they are removed entirely.

Algorithm:

1. Use three pointers:
   • pre: points before current group
   • curr: start of current group
   • next: scans to end of current group
2. For each value:
   • Scan next until different value found
   • If curr ≠ next: duplicates found, skip group
   • If curr = next: unique value, keep it
3. Use dummy node to handle head deletion

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public ListNode deleteDuplicates(ListNode head) {
    ListNode dummy = new ListNode(0, head);
    ListNode pre = dummy, curr = head, next = head;

    while (curr != null) {
        // Find end of current group
        while (next.next != null && next.next.val == next.val)
            next = next.next;

        if (curr != next) {
            // Duplicates found, skip entire group
            pre.next = next.next;
            curr = next.next;
            next = curr;
        } else {
            // No duplicates, keep current node
            pre = curr;
            curr = curr.next;
            next = curr;
        }
    }
    
    return dummy.next; 
}

Python Solution:

def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    pre = dummy
    curr = next = head
    
    while curr:
        # Find end of current group
        while next.next and next.next.val == next.val:
            next = next.next
            
        if curr != next:
            # Skip duplicates
            pre.next = next.next
            curr = next.next
            next = curr
        else:
            # Keep unique value
            pre = curr
            curr = curr.next
            next = curr
    
    return dummy.next

C++ Solution:

ListNode* deleteDuplicates(ListNode* head) {
    ListNode* dummy = new ListNode(0, head);
    ListNode *pre = dummy, *curr = head, *next = head;
    
    while (curr) {
        // Scan for duplicates
        while (next->next && next->next->val == next->val)
            next = next->next;
            
        if (curr != next) {
            // Remove duplicate group
            pre->next = next->next;
            curr = next->next;
            next = curr;
        } else {
            // Keep unique value
            pre = curr;
            curr = curr->next;
            next = curr;
        }
    }
    
    ListNode* result = dummy->next;
    delete dummy;
    return result;
}