< Back





82. Remove Duplicates from Sorted List II

A fun question, pretty straightforward. Given a sorted linked list, delete all nodes that have
duplicate members, including the original node. This is kinda like running uniq on a sorted linked
list.

We can solve this by first creating our quintessential dummy node that points to the head of the
original linked list - just in case we end up deleting the first element. We iterate through the
linked list, and if we detect that our next node is a duplice to the next next node, we track the
duplicate value. We continue to unlink the next node while it exists and its value is equal to the
duplicate value.

If the next node is not a duplicate, we just continue our iteration.

The solution is as follows:


  class Solution:
      def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
          dummy = curr = ListNode(-1, head)

          while curr:
              if curr.next and curr.next.next and curr.next.val == curr.next.next.val:
                  dup = curr.next.val

                  while curr.next and curr.next.val == dup:
                      curr.next = curr.next.next
              else:
                  curr = curr.next

          return dummy.next


_ Time Complexity:

  O(n) - We traverse all nodes within the linked list.

_ Space Complexity:

  O(1) - We maintain pointers that occupy constant space.