Remove Duplicates from Sorted List II

Problem Description

Ah, the classic “Remove Duplicates from Sorted List II” problem! It’s like that one friend who insists on bringing the same dish to every potluck. You know, the one who thinks their famous potato salad is the only thing anyone wants to eat. But alas, we need to clear the table and make room for some variety!

In this problem, you are given a sorted linked list, and your task is to remove all nodes that have duplicate numbers, leaving only distinct numbers. So, if you have a list that looks like 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5, you should end up with 1 -> 2 -> 5.

Imagine you’re at a party, and you see a group of people wearing the same outfit. You’d want to send them home to change, right? Well, that’s what we’re doing here—sending the duplicates packing!

Code Solution


class Solution {
  public ListNode deleteDuplicates(ListNode head) {
    ListNode dummy = new ListNode(0, head);
    ListNode prev = dummy;

    while (head != null) {
      while (head.next != null && head.val == head.next.val)
        head = head.next;
      if (prev.next == head)
        prev = prev.next;
      else
        prev.next = head.next;
      head = head.next;
    }

    return dummy.next;
  }
}

Approach Explanation

The approach here is quite straightforward. We use a dummy node to simplify the handling of edge cases, like when the head itself is a duplicate. We traverse the list while checking for duplicates. If we find duplicates, we skip them and link the previous node to the next distinct node. It’s like playing a game of musical chairs—when the music stops (i.e., we find duplicates), we just skip over those who are already seated!

Time and Space Complexity

Complexity Type	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 are using a constant amount of space (the dummy node and a few pointers).

Real-World Example

Think of a grocery store where you have a shelf full of identical cereal boxes. If you want to make room for new flavors, you need to remove the duplicates. So, if you have Cheerios, Cheerios, Cornflakes, Cornflakes, Frosted Flakes, you’ll end up with just Cheerios, Cornflakes, Frosted Flakes. That’s exactly what our code does—clearing out the duplicates to make room for the unique items!