Remove Duplicates from Sorted List II

• Create a HashMap to store the frequency of each number.
• Traverse the linked list from head to tail, and for each node, update its value's count in the hash map.
• Initialize a sentinel node and a tail pointer pointing to it. This will be the start of our new list.
• Traverse the original linked list again.
• For each node, look up its value in the hash map.
• If the count is 1, create a new node with this value and append it to the list pointed to by tail. Move tail to this new node.
• Return sentinel.next.

We first iterate through the entire linked list to populate a hash map (or a frequency array since the value range is small) with the counts of each node value. After counting, we create a new sentinel (dummy) node to simplify the construction of the result list. A tail pointer will track the end of this new list. We then iterate through the original list again. For each node, we check its value's frequency in our hash map. If the frequency is exactly 1, it means the node is unique. We create a new node with this value and append it to our result list, advancing the tail pointer. Finally, we return the next of our sentinel node, which is the head of the new, filtered list.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode deleteDuplicates(ListNode head) {13        if (head == null) {14            return null;15        }16 17        Map<Integer, Integer> counts = new HashMap<>();18        ListNode current = head;19        while (current != null) {20            counts.put(current.val, counts.getOrDefault(current.val, 0) + 1);21            current = current.next;22        }23 24        ListNode sentinel = new ListNode(0);25        ListNode tail = sentinel;26 27        current = head;28        while (current != null) {29            if (counts.get(current.val) == 1) {30                tail.next = new ListNode(current.val);31                tail = tail.next;32            }33            current = current.next;34        }35 36        return sentinel.next;37    }38}

• Define a recursive function deleteDuplicates(node).
• Base Case: If node is null, return null.
• Check if node.next exists and node.val == node.next.val.
• If true (duplicate found):
  • Create a temporary pointer temp and move it forward as long as the nodes have the same value as node.
  • Return the result of deleteDuplicates(temp).
• If false (node is unique):
  • The node is part of the result. Recursively process the rest of the list by calling deleteDuplicates(node.next).
  • Set node.next to the result of the recursive call.
  • Return node.

The base case for the recursion is an empty list (head == null), in which case we return null. We check if the current head node is part of a duplicate sequence by comparing its value with the next node's value (head.next != null && head.val == head.next.val). If it is a duplicate, we must discard all nodes with this value. We use a loop to advance a pointer past all nodes with the same value. Then, we make a recursive call with the first node that has a different value. The result of this recursive call is the result for the current level. If the head is not a duplicate, we know it must be included in the final list. So, we keep it and recursively call the function on head.next. The result of this sub-problem becomes the new head.next. We then return the head.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode deleteDuplicates(ListNode head) {13        // Base case: empty list or a single node list14        if (head == null || head.next == null) {15            return head;16        }17 18        // Check if the head is part of a duplicate sequence19        if (head.val == head.next.val) {20            // Skip all nodes with the same value as head21            ListNode current = head;22            while (current != null && current.val == head.val) {23                current = current.next;24            }25            // Recursively call on the rest of the list26            return deleteDuplicates(current);27        } else {28            // Head is not a duplicate, keep it.29            // Recursively call on the rest of the list and connect it30            head.next = deleteDuplicates(head.next);31            return head;32        }33    }34}

• Create a sentinel node and set its next to the original head.
• Initialize a pred (predecessor) pointer to the sentinel.
• Initialize a current pointer to head.
• Loop while current is not null:
  • Check if current is the start of a duplicate sequence (current.next != null && current.val == current.next.val).
  • If true (duplicate found):
    • Move current forward until it's the last node in the duplicate sequence.
    • Update pred.next to point to current.next, effectively skipping the entire duplicate sequence.
  • If false (node is unique):
    • Move pred to the next node (pred = pred.next).
  • Move current to the next node (current = current.next).
• Return sentinel.next.

We introduce a sentinel (or dummy) node, which points to the original head. This helps manage edge cases, such as when the head of the list is a duplicate and needs to be removed. We use a pred (predecessor) pointer, initialized to the sentinel. This pointer will always point to the node just before a potential sequence of duplicates. We iterate through the list using a head pointer. In each step, we check if head is the beginning of a duplicate sequence (i.e., head.next != null && head.val == head.next.val). If it is, we enter an inner loop to skip all nodes that are part of this duplicate sequence. We keep moving head forward until it points to a node with a different value. After the inner loop, head is the last node of the duplicate sequence. We then link pred.next to head.next, effectively removing the entire duplicate sequence. If head is not the start of a duplicate sequence, it means this node is unique and should be kept. We simply move our pred pointer forward to pred.next. In both cases, we advance head to the next node to continue the process. Finally, we return sentinel.next.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode deleteDuplicates(ListNode head) {13        // Use a sentinel node to handle deletion of the head node14        ListNode sentinel = new ListNode(0, head);15 16        // Predecessor is the last node before the sublist of duplicates17        ListNode pred = sentinel;18        19        while (head != null) {20            // If it's a beginning of duplicates sublist21            // i.e. head.next is not null and its value is the same as head22            if (head.next != null && head.val == head.next.val) {23                // Move till the end of duplicates sublist24                while (head.next != null && head.val == head.next.val) {25                    head = head.next;26                }27                // Skip all duplicates28                pred.next = head.next;29            // Otherwise, move predecessor30            } else {31                pred = pred.next;32            }33            34            // Move forward35            head = head.next;36        }37        return sentinel.next;38    }39}