https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii

Idea here is to traverse our linked list and use two pointers:

  1. slow is for node just before duplications begins
  2. fast is for the last node of duplication group.

Now, we traverse nodes and do the following steps:

  1. while we have fast.next and its value is equal to fast, it means, than we have one more duplicate, so we move fast pointer to the right.
  2. If it happen, that slow.next equal to fast, it means, that we have only 1 element in group of duplicated elements, that is we do not need to delete it and we move both pointers to right.
  3. If it happen, that slow.next is not equal to fast, it means, that we need to skip group of duplicated elements: we create new connection: slow.next = fast.next, and also we allocate fast = slow.next. Note, that now we still have the original property: slow points to node before group of duplicated elements and fast will be the last element of this group (after while fast.next and fast.val == fast.next.val: line)

Complexity: time complexity is O(n): we traverse our list at most twice for each of the pointers. Space complexity is O(1): we did not use any additional memory here.

class Solution:
    def deleteDuplicates(self, head):
        dummy = ListNode(-1)
        dummy.next = head
        fast, slow = head, dummy
        while fast:
            while fast.next and fast.val == fast.next.val:
                fast = fast.next
            if slow.next == fast:
                slow, fast = slow.next, fast.next
            else:
                slow.next = fast.next
                fast = slow.next
                
        return dummy.next

If you like the solution, you can upvote it on leetcode discussion section: Problem 0082