Leetcode 82. Remove Duplicates from Sorted List II

📅2023-07-23🧐88

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

We have two simple approaches to this question

Hashmap or Hashset
Slow and faster pointer (two pointer)

To use which kind of solution is depend on the needs.

Hashset

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        need_to_remove = set()
        curr = head

        while curr and curr.next:
            if curr.val == curr.next.val:
                need_to_remove.add(curr.val)
            curr = curr.next

        nhead = ListNode()
        curr, ncurr = head, nhead
        while curr:
            if curr.val in need_to_remove:
                curr = curr.next
                continue
            ncurr.next = ListNode(curr.val)
            ncurr = ncurr.next
            curr = curr.next


        return nhead.next

This solution is in O(2n) => O(n) time, so it's quick.

Two pointer

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        curr = s = ListNode(0, head)

        while head:
            if head.next and head.val == head.next.val:
                while head.next and head.val == head.next.val:
                    head = head.next
                curr.next = head.next
            else:
                curr = curr.next
            
            head = head.next
        return s.next

This solution is also in O(n) time. But we could say it's faster, since only one loop there.