algoadvance

Leetcode 82. Remove Duplicates from Sorted List II

Problem Statement

You are given the head of a sorted linked list. Remove all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

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

Example 2:

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

Clarifying Questions

  1. Is the list guaranteed to be sorted in non-decreasing order?
    • Yes, the list is sorted.
  2. Do we receive an empty linked list as input?
    • Yes, the list could be empty, and we should handle it appropriately.
  3. Can the list have all elements as duplicates?
    • Yes, and in that case, the output should be an empty list.

Strategy

To solve this problem:

  1. We will traverse the linked list while keeping track of the current node and a boolean indicating whether this node is a duplicate.
  2. Use a dummy head to easily handle edge cases where the head itself needs to be removed.
  3. For each node, we will:
    • Skip over the nodes which are duplicates.
    • If we encounter nodes that are not duplicates, we will include them in our new linked list.
  4. Use pointers to omit nodes that are duplicates and move the pointers appropriately.

Code

Here is the code implementation in Java:

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;

        ListNode dummy = new ListNode(0, head);
        ListNode pred = dummy;  // predecessor, the last node before the sublist of duplicates

        while (head != null) {
            if (head.next != null && head.val == head.next.val) {
                // Skip nodes whose value are the same as the current node's value
                while (head.next != null && head.val == head.next.val) {
                    head = head.next;
                }
                pred.next = head.next;
            } else {
                pred = pred.next;
            }
            head = head.next;
        }

        return dummy.next;
    }
}

Time Complexity

The time complexity for this solution is O(n) because:

Space Complexity

The space complexity is O(1) because:

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI