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.

Example 1:

1Input: head = [1,2,3,3,4,4,5]
2Output: [1,2,5]

Example 2:

1Input: head = [1,1,1,2,3]
2Output: [2,3]

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.

Solution

This problem is similar to problem 0083 Remove Duplicates from Sorted List except that this one requires us to remove all duplicates. In order to remove duplicates from first node, we need the previous node. If first element is duplicate, how do we get the node before that? The idea is to create a dummy first node which points to head and then using that check for all nodes that are duplicates and remove them if needed. In this case, we can easily clean up the duplicates by checking with the next node and moving pointer forward each time there are duplicates. However, once we have removed duplicates, there will still be single instance of this number which is left to clear. Due to this, we have to use inner while loop and outside of that we move the previous pointer to next of the leftover duplicate.

 1class Solution {
 2    public ListNode deleteDuplicates(ListNode head) {
 3        if (head == null) {
 4            return null;
 5        }
 6        ListNode dummy = new ListNode(0, head);
 7        ListNode previous = dummy, current = head;
 8        while (current != null) {
 9            // If current is duplicate
10            if (current.next != null && current.val == current.next.val) {
11                // Make list unique
12                while (current.next != null && current.val == current.next.val) {
13                    current = current.next;
14                }
15                // Remove that single instance which is duplicate from the list
16                previous.next = current.next;
17            } else {
18                // If current is not duplicate
19                previous = previous.next;
20            }
21            current = current.next;
22        }
23        return dummy.next;
24    }
25}
  • Time Complexity: O(n)
  • Space Complexity: O(1)