82. Remove Duplicates from Sorted List II

Medium

Problem Description

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.

Examples

Example 1:
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
Explanation: The numbers 3 and 4 appear multiple times, so they are removed.

Example 2:
Input: head = [1,1,1,2,3]
Output: [2,3]
Explanation: The number 1 appears multiple times, so all occurrences are removed.
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def deleteDuplicates(head: Optional[ListNode]) -> Optional[ListNode]:
    # Handle empty list or single node
    if not head or not head.next:
        return head
    
    # Create dummy node to handle cases where head needs to be removed
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
    curr = head
    
    while curr and curr.next:
        # Skip all duplicates
        if curr.val == curr.next.val:
            while curr.next and curr.val == curr.next.val:
                curr = curr.next
            curr = curr.next
            prev.next = curr
        else:
            prev = curr
            curr = curr.next
    
    return dummy.next

Java Solution


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // Handle empty list or single node
        if (head == null || head.next == null) {
            return head;
        }
        
        // Create dummy node to handle cases where head needs to be removed
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        
        while (curr != null && curr.next != null) {
            // Skip all duplicates
            if (curr.val == curr.next.val) {
                while (curr.next != null && curr.val == curr.next.val) {
                    curr = curr.next;
                }
                curr = curr.next;
                prev.next = curr;
            } else {
                prev = curr;
                curr = curr.next;
            }
        }
        
        return dummy.next;
    }
}

C++ Solution


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // Handle empty list or single node
        if (!head || !head->next) {
            return head;
        }
        
        // Create dummy node to handle cases where head needs to be removed
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prev = dummy;
        ListNode* curr = head;
        
        while (curr && curr->next) {
            // Skip all duplicates
            if (curr->val == curr->next->val) {
                while (curr->next && curr->val == curr->next->val) {
                    curr = curr->next;
                }
                curr = curr->next;
                prev->next = curr;
            } else {
                prev = curr;
                curr = curr->next;
            }
        }
        
        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};

JavaScript Solution


/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    // Handle empty list or single node
    if (!head || !head.next) {
        return head;
    }
    
    // Create dummy node to handle cases where head needs to be removed
    const dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    let curr = head;
    
    while (curr && curr.next) {
        // Skip all duplicates
        if (curr.val === curr.next.val) {
            while (curr.next && curr.val === curr.next.val) {
                curr = curr.next;
            }
            curr = curr.next;
            prev.next = curr;
        } else {
            prev = curr;
            curr = curr.next;
        }
    }
    
    return dummy.next;
};

C# Solution


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        // Handle empty list or single node
        if (head == null || head.next == null) {
            return head;
        }
        
        // Create dummy node to handle cases where head needs to be removed
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        
        while (curr != null && curr.next != null) {
            // Skip all duplicates
            if (curr.val == curr.next.val) {
                while (curr.next != null && curr.val == curr.next.val) {
                    curr = curr.next;
                }
                curr = curr.next;
                prev.next = curr;
            } else {
                prev = curr;
                curr = curr.next;
            }
        }
        
        return dummy.next;
    }
}

Complexity Analysis

Solution Explanation

This solution uses a two-pointer approach with a dummy node:

Key points: