Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        dummy = ListNode(0, head)
        prev = dummy
        curr = head

        while curr:
            duplicate = False
            while curr.next and curr.val == curr.next.val:
                curr = curr.next
                duplicate = True
            if duplicate:
                prev.next = curr.next
            else:
                prev = prev.next
            curr = curr.next
        return dummy.next
      

/**
 * 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) {
        ListNode dummy(0, head);
        ListNode* prev = &dummy;
        ListNode* curr = head;
        while (curr) {
            bool duplicate = false;
            while (curr->next && curr->val == curr->next->val) {
                curr = curr->next;
                duplicate = true;
            }
            if (duplicate) {
                prev->next = curr->next;
            } else {
                prev = prev->next;
            }
            curr = curr->next;
        }
        return dummy.next;
    }
};
      

/**
 * 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) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        ListNode curr = head;
        while (curr != null) {
            boolean duplicate = false;
            while (curr.next != null && curr.val == curr.next.val) {
                curr = curr.next;
                duplicate = true;
            }
            if (duplicate) {
                prev.next = curr.next;
            } else {
                prev = prev.next;
            }
            curr = curr.next;
        }
        return dummy.next;
    }
}
      

/**
 * 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) {
    let dummy = new ListNode(0, head);
    let prev = dummy;
    let curr = head;
    while (curr) {
        let duplicate = false;
        while (curr.next && curr.val === curr.next.val) {
            curr = curr.next;
            duplicate = true;
        }
        if (duplicate) {
            prev.next = curr.next;
        } else {
            prev = prev.next;
        }
        curr = curr.next;
    }
    return dummy.next;
};
      

Problem Description

The problem "Remove Duplicates from Sorted List II" asks you to process a singly linked list where the values are sorted in ascending order. Your goal is to remove all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

In other words, if a value appears more than once in the list, you must remove all occurrences of that value, not just the duplicates. The output should be the head of the modified linked list containing only unique values, in sorted order.

• The input is the head node head of a singly linked list.
• Each node contains an integer value val and a pointer next to the next node.
• You must return the head of the list after removing all nodes with duplicate numbers.
• You must not create new nodes for distinct elements; only adjust pointers as needed.

Thought Process

At first glance, one might consider traversing the list and removing consecutive duplicates as we go. However, the problem requires us to remove all instances of any value that appears more than once, not just the extra copies. This makes the problem trickier than the classic "remove duplicates" problem.

A naive approach could be to use a hash map to count occurrences, but since the list is already sorted, we can take advantage of this property. By comparing each node to its neighbors, we can detect duplicates in a single pass.

To handle edge cases (such as the head itself being a duplicate), we often use a "dummy" node at the start of the list. This simplifies pointer manipulation and ensures we don't lose track of the new head.

Solution Approach

• Step 1: Use a Dummy Node
  • Create a dummy node whose next points to the head of the list.
  • This helps in cases where the head itself is removed.
• Step 2: Initialize Pointers
  • Use two pointers: prev (initially at dummy) and curr (at head).
• Step 3: Traverse and Detect Duplicates
  • While traversing, check if curr has the same value as curr.next.
  • If so, move curr forward as long as the next node has the same value.
• Step 4: Remove All Occurrences of Duplicates
  • If duplicates were found, set prev.next to curr.next (skipping all duplicates).
  • If not, move prev forward to curr.
• Step 5: Continue Traversal
  • Move curr to the next node and repeat until the end of the list.
• Step 6: Return the Result
  • Return dummy.next as the new head of the modified list.

This approach is efficient because it only requires a single pass through the list and uses no extra memory beyond a few pointers.

Example Walkthrough

Let's consider the input list: 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5

1. Start: Dummy node added before 1.
2. First node (1): Next value is 2 (not a duplicate), so move prev to 1.
3. Next node (2): Next value is 3 (not a duplicate), move prev to 2.
4. Next node (3): Next value is 3 (duplicate detected). Move curr forward to skip all 3s.
5. Set prev.next to node after last 3 (which is 4), removing all 3s.
6. Next node (4): Next value is 4 (duplicate detected). Move curr forward to skip all 4s.
7. Set prev.next to node after last 4 (which is 5), removing all 4s.
8. Next node (5): No duplicate, move prev to 5.
9. End of list reached.

The resulting list is: 1 -> 2 -> 5

Time and Space Complexity

• Brute-force approach:
  • If we used a hash map to count occurrences, it would require two passes: one to count, one to remove. Time: O(n). Space: O(n) for the map.
• Optimized approach (current solution):
  • Single pass through the list, so Time: O(n) where n is the number of nodes.
  • Only a few extra pointers are used, so Space: O(1) (constant extra space).

The optimized solution is both time and space efficient, leveraging the sorted property of the input.

Summary

In summary, the key to solving "Remove Duplicates from Sorted List II" is recognizing that the sorted property allows us to detect and remove all duplicates in a single pass, using just a few pointers and a dummy node for simplicity. The solution is elegant because it avoids extra space and handles all edge cases, including duplicates at the head and tail, with minimal code.