Remove Duplicates from Sorted List

• Initialize an empty HashSet called seen.
• Create a dummy node to act as the starting point for the new, de-duplicated list.
• Create a newTail pointer, initially pointing to dummy.
• Initialize a current pointer to the head of the input list.
• Iterate through the input list with the current pointer until it becomes null.
• Inside the loop, check if current.val exists in the seen set.
• If current.val is not in seen, add it to the set, create a new node with this value, append it to the new list (newTail.next), and move newTail to this new node.
• If current.val is already in seen, do nothing.
• Move current to the next node in the original list.
• After the loop, return dummy.next, which is the head of the new list.

We can solve this problem by creating a new linked list that will only contain the unique elements from the original list.

To do this, we'll use a HashSet to store the values of the nodes we've already encountered. We'll iterate through the original list, and for each node, we check if its value is already in our hash set.

• If the value is not in the set, it's the first time we're seeing this element. We add it to our new list and also add its value to the hash set.
• If the value is already in the set, it's a duplicate, so we simply skip it and move to the next node in the original list.

We use a dummy head node to simplify the process of building the new 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 */11import java.util.HashSet;12import java.util.Set;13 14class Solution {15    public ListNode deleteDuplicates(ListNode head) {16        if (head == null) {17            return null;18        }19 20        Set<Integer> seen = new HashSet<>();21        ListNode dummy = new ListNode(0); // Dummy head for the new list22        ListNode newTail = dummy;23        ListNode current = head;24 25        while (current != null) {26            if (!seen.contains(current.val)) {27                seen.add(current.val);28                newTail.next = new ListNode(current.val);29                newTail = newTail.next;30            }31            current = current.next;32        }33 34        return dummy.next;35    }36}

• Initialize a pointer current to the head of the list.
• Handle the edge case where the list is empty or has only one node by returning head.
• Loop as long as current and current.next are not null.
• Inside the loop, compare current.val with current.next.val.
• If they are equal, it's a duplicate. Modify the next pointer of the current node to skip the duplicate: current.next = current.next.next.
• If they are not equal, the next element is unique. Move the current pointer forward: current = current.next.
• After the loop terminates, return the original head, which now points to the de-duplicated list.

We can solve this problem with a single pass and without using any extra space. The key insight is that because the list is sorted, we can just compare each node with its immediate successor.

We'll use a pointer, let's call it current, that starts at the head of the list. We then look at the next node, current.next.

• If current.val is the same as current.next.val, we know current.next is a duplicate. To remove it, we can simply bypass it by setting current.next to current.next.next. We don't advance current yet, because the new current.next could also be a duplicate (e.g., in a list like 1 -> 1 -> 1).
• If current.val is different from current.next.val, it means there's no duplicate, so we can safely move current one step forward to current.next.

We repeat this process until current or current.next becomes null.

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        // Start with the head of the list14        ListNode current = head;15 16        // Traverse the list as long as the current node and the next node are not null17        while (current != null && current.next != null) {18            // If the current node's value is the same as the next node's value19            if (current.val == current.next.val) {20                // Skip the duplicate node21                current.next = current.next.next;22            } else {23                // Move to the next node24                current = current.next;25            }26        }27        28        // Return the modified head of the list29        return head;30    }31}