Remove Duplicates From Sorted List

83.Remove Duplicates from Sorted List

Linked List

Two Pointers

Problem Statement:

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Example:

Input:

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

→

Output:

[1→2→3]

Each value appears exactly once in the output.

Algorithm:

1. Single pointer approach as list is sorted
2. For each node, while next node has same value:
   • Skip over duplicates by moving next pointer
   • Continue until finding different value
3. Move to next unique node

Complexity:

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

Java Solution:

public ListNode deleteDuplicates(ListNode head) {
    ListNode curr = head;
    
    while (curr != null && curr.next != null) {
        // Skip all nodes with same value
        while (curr.next != null && curr.val == curr.next.val) 
            curr.next = curr.next.next;
          
        curr = curr.next;  
    }
    
    return head;   
}

Python Solution:

def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    curr = head
    
    while curr and curr.next:
        # Skip duplicates
        while curr.next and curr.val == curr.next.val:
            curr.next = curr.next.next
        
        curr = curr.next
    
    return head

C++ Solution:

ListNode* deleteDuplicates(ListNode* head) {
    ListNode* curr = head;
    
    while (curr && curr->next) {
        // Skip all duplicates
        while (curr->next && curr->val == curr->next->val) 
            curr->next = curr->next->next;
        
        curr = curr->next;
    }
    
    return head;
}