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*.

**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]

**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.

The core challenge of this problem is to remove all nodes that have duplicate values from a sorted linked list, ensuring that only distinct values remain. This is significant in scenarios where data integrity and uniqueness are crucial, such as in databases or data processing pipelines.

Common pitfalls include not handling edge cases like an empty list or a list where all elements are duplicates.

To solve this problem, we can use a two-pointer technique to traverse the linked list and identify duplicates. Here's a step-by-step approach:

A naive solution would involve using nested loops to compare each node with every other node, but this would result in a time complexity of O(n^2), which is inefficient for larger lists.

An optimized solution involves using a single pass through the list with a dummy node to handle edge cases more gracefully. This approach ensures a time complexity of O(n).

1. Create a dummy node that points to the head of the list.

2. Use a pointer to traverse the list, checking for duplicates.

3. If duplicates are found, skip all nodes with the duplicate value.

4. Continue until the end of the list is reached.

```
/**
* Definition for singly-linked list.
* 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) {
// Create a dummy node to handle edge cases
ListNode dummy = new ListNode(0);
dummy.next = head;
// Pointer to traverse the list
ListNode current = dummy;
while (current.next != null && current.next.next != null) {
// If the current node's next value equals the next's next value, we have duplicates
if (current.next.val == current.next.next.val) {
int duplicateVal = current.next.val;
// Skip all nodes with the duplicate value
while (current.next != null && current.next.val == duplicateVal) {
current.next = current.next.next;
}
} else {
// Move to the next node
current = current.next;
}
}
return dummy.next;
}
}
```

The time complexity of this approach is O(n) because we traverse the list only once. The space complexity is O(1) as we are using a constant amount of extra space.

Potential edge cases include:

- An empty list: The function should return an empty list.
- A list with all duplicate values: The function should return an empty list.
- A list with no duplicates: The function should return the original list.

To test the solution comprehensively, consider the following test cases:

- head = [] (empty list)
- head = [1,1,1,1] (all duplicates)
- head = [1,2,3,4,5] (no duplicates)
- head = [1,1,2,3,3,4,5,5] (mixed duplicates)

When approaching such problems, it's essential to:

- Understand the problem constraints and edge cases.
- Think about the most efficient way to traverse and manipulate the data structure.
- Break down the problem into smaller, manageable steps.

Removing duplicates from a sorted linked list is a common problem that tests your understanding of linked list manipulation and traversal. By using a dummy node and a single-pass approach, we can achieve an efficient solution with a time complexity of O(n).

For further reading and practice, consider the following resources: