82. Remove Duplicates from Sorted List II

Intuition

We need to traverse the linked list and remove nodes with duplicate values. After removing duplicates, the linked list should only contain nodes with unique values in sorted order.

Approach

1. Dummy Node Initialization: Use a dummy node to handle cases where the head itself might be removed due to duplicates.
2. Traversal and Removal: - Initialize a pointer (prev) to keep track of the node before the current node being checked. - Use another pointer (curr) to traverse through the list. - Whenever a duplicate is found (i.e., curr.next exists and has the same value as curr), remove all nodes including curr that have duplicate values. - Connect prev.next directly to the next node after the duplicates are removed.
3. Edge Cases: - Handle cases where duplicates exist at the beginning, middle, or end of the list. - Ensure the last node is properly connected to None to terminate the list.
4. Return: Return dummy.next, which points to the head of the modified linked list.

Complexity

##Time Complexity:

O(n), where n is the number of nodes in the linked list. We traverse the list once.

Space Complexity: O(1), since we use only a constant amount of extra space regardless of the input size.

Code

C++

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* output = new ListNode(0, head);
        ListNode* pre = output;
        
        while (head) {
            if (head->next && head->val == head->next->val) {
                while (head->next && head->val == head->next->val) {
                    head = head->next;
                }
                pre->next = head->next;
            } else {
                pre = pre->next;
            }
            head = head->next;
        }
        
        return output->next;
    }
};

Python

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        output = ListNode(0, head)
        pre = output
        
        while head:
            if head.next and head.val == head.next.val:
                while head.next and head.val == head.next.val:
                    head = head.next
                pre.next = head.next
            else:
                pre = pre.next
            head = head.next
        
        return output.next

Java

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode output = new ListNode(0, head);
        ListNode pre = output;
        
        while (head != null) {
            if (head.next != null && head.val == head.next.val) {
                while (head.next != null && head.val == head.next.val) {
                    head = head.next;
                }
                pre.next = head.next;
            } else {
                pre = pre.next;
            }
            head = head.next;
        }
        
        return output.next;
    }
}

JavaScript

var deleteDuplicates = function(head) {
    if(!head || !head.next) {
        return head
    }
    let output = new ListNode(0, head), pre = output
    while(head) {
        if(head.next && head.val === head.next.val) {
            while(head.next && head.val === head.next.val) {
                head = head.next
            }
            pre.next = head.next
        } else {
            pre = pre.next
        }
        head = head.next
    }
    return output.next    
};