Naive Solution

A brute force solution to this problem would involve iterating through the linked list, keeping track of the frequency of each value, and then constructing a new linked list containing only the distinct values. This approach would require extra space to store the frequencies.

Algorithm:

1. Traverse the linked list and store the frequency of each value in a hash map.
2. Create a new linked list.
3. Traverse the hash map. If a value has a frequency of 1, add it to the new linked list in sorted order.
4. Return the head of the new linked list.

Big O Analysis:

• Time Complexity: O(N), where N is the number of nodes in the linked list. This is because we traverse the list once to count frequencies and then potentially iterate through the list again when building the new list
• Space Complexity: O(N), where N is the number of nodes, due to the hash map potentially storing each unique value.

Optimal Solution

An optimal solution can be achieved by iterating through the linked list and removing the duplicate nodes in place. This approach requires only constant extra space.

Algorithm:

1. Create a dummy node to simplify the handling of the head of the list.
2. Initialize two pointers, prev and curr, to the dummy node and the head of the list, respectively.
3. Iterate through the linked list:
   • If the current node has a duplicate value (i.e., curr.next != null && curr.val == curr.next.val):
     • Skip all duplicate nodes.
     • Update prev.next to point to the node after the duplicates.
   • Otherwise:
     • Move prev to curr.
   • Move curr to curr.next.
4. Return the next node of the dummy node, which is the head of the modified linked list.

Edge Cases:

• Empty list: The algorithm should handle an empty list gracefully by returning null.
• List with no duplicates: The algorithm should correctly return the original list.
• List with all duplicates: The algorithm should return an empty list.
• Duplicates at the beginning of the list: The dummy node helps handle this case.

Code:

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

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

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

        return dummy.next;
    }
}

Big O Analysis:

• Time Complexity: O(N), where N is the number of nodes in the linked list, as we traverse the list once.
• Space Complexity: O(1), as we use only constant extra space for the pointers.