Remove Duplicates from Sorted List: Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Example 1:

Input: head = [1,1,2]
Output: [1,2]

Example 2:

Input: head = [1,1,2,3,3]
Output: [1,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.

Try this Problem on your own or check similar problems:

1. Remove Linked List Elements
2. Remove Duplicates from Sorted List II

Solution:

public ListNode deleteDuplicates(ListNode head) {
    if (head == null) return null;

    ListNode dummy = new ListNode(-1, head), curr = dummy.next;

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

    return dummy.next;
}

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

Explanation:

The problem is really similar to the Remove Linked List Elements where we have a sentinel node and we iterate through list and for each node check if it’s next node has the same value, if it has we relink the current node to point to the next node and repeat the process until we find a node with a value that’s different than the value at current node. Dummy node will be pointing to the new head so we just have to return dummy.next.