Remove Duplicates from Sorted List II

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.

For example:

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

Input: head = [1,1,1,2,3] Output: [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 requires us to remove all nodes with duplicate values from a sorted linked list, leaving only the distinct values. Since the list is sorted, we can iterate through it and identify consecutive duplicate nodes. A dummy node is used to simplify the handling of the head of the list.

## Naive Approach

A straightforward approach involves iterating through the linked list while keeping track of the previous and current nodes. Whenever we encounter a sequence of duplicate nodes, we skip over all of them, updating the `next` pointer of the previous node to point to the node after the sequence of duplicates.

## Optimal Approach

We can optimize the approach by using a dummy node to handle edge cases where the head of the list contains duplicates. This simplifies the code and ensures that the head is properly updated if necessary.

```python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def delete_duplicates(head):
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
    curr = head

    while curr:
        if curr.next and curr.val == curr.next.val:
            # Skip all duplicate nodes
            while curr.next and curr.val == curr.next.val:
                curr = curr.next
            prev.next = curr.next  # Remove duplicates
        else:
            prev = curr  # Move previous pointer forward

        curr = curr.next  # Move current pointer forward

    return dummy.next

# Helper function to create linked list from a list
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    curr = head
    for i in range(1, len(arr)):
        curr.next = ListNode(arr[i])
        curr = curr.next
    return head

# Helper function to convert linked list to a list for testing
def linked_list_to_list(head):
    result = []
    curr = head
    while curr:
        result.append(curr.val)
        curr = curr.next
    return result

# Example usage
# Example 1
head1 = create_linked_list([1, 2, 3, 3, 4, 4, 5])
result1 = delete_duplicates(head1)
print(linked_list_to_list(result1))  # Output: [1, 2, 5]

# Example 2
head2 = create_linked_list([1, 1, 1, 2, 3])
result2 = delete_duplicates(head2)
print(linked_list_to_list(result2))  # Output: [2, 3]

# Example 3
head3 = create_linked_list([1, 1, 2, 2, 3, 3])
result3 = delete_duplicates(head3)
print(linked_list_to_list(result3)) # Output: []

# Example 4
head4 = create_linked_list([1, 2, 3])
result4 = delete_duplicates(head4)
print(linked_list_to_list(result4)) # Output: [1, 2, 3]

# Example 5
head5 = create_linked_list([])
result5 = delete_duplicates(head5)
print(linked_list_to_list(result5)) # Output: []

Big(O) Run-time Analysis

The algorithm iterates through the linked list once. In the worst-case scenario, each node might be visited to check for duplicates. Therefore, the run-time complexity is O(n), where n is the number of nodes in the linked list.

Big(O) Space Usage Analysis

The algorithm uses a constant amount of extra space for the dummy, prev, and curr pointers, regardless of the size of the input linked list. Thus, the space complexity is O(1), indicating constant space usage.

Edge Cases

1. Empty List: If the input list is empty, the function should return an empty list. This is handled correctly by the initial check and the way the dummy node is used.
2. List with No Duplicates: If there are no duplicates, the function should return the original list. The algorithm correctly handles this as it only modifies the list when duplicates are found.
3. List with All Duplicates: If all elements in the list are duplicates, the function should return an empty list. The while loop condition curr.next and curr.val == curr.next.val ensures that all duplicate nodes are skipped, and prev.next is set to curr.next, effectively removing all nodes.
4. Duplicates at the Beginning: If the head of the list contains duplicates, the dummy node ensures correct handling by updating the head pointer.
5. Duplicates at the End: If the tail of the list contains duplicates, the algorithm correctly removes them without causing any issues.