Teaching Kids Programming – Remove Duplicates from Sorted Linked List (Using Hash Set)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Remove Duplicates from Sorted Linked List

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.

Remove Duplicates from Sorted Linked List (Using Hash Set)

Apart from Two Pointer: Teaching Kids Programming – Remove Duplicates from Sorted Linked List (Two Pointer Algorithm), we can use a hash set to remember the nodes that we have visited, and remove the duplicate nodes along the way when we traverse the linked list. This approach can be also applied to the general case when the linked list is not sorted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 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:
            return None
        prev = None
        cur = head
        seen = set()
        while cur:
            if cur.val in seen:
                node = cur
                prev.next = cur.next
                del node
            else:
                seen.add(cur.val)
                prev = cur
            cur = cur.next
        return head

# 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:
            return None
        prev = None
        cur = head
        seen = set()
        while cur:
            if cur.val in seen:
                node = cur
                prev.next = cur.next
                del node
            else:
                seen.add(cur.val)
                prev = cur
            cur = cur.next
        return head

The time complexity is O(N), so is the space complexity because we are using a hash set.

Remove Duplicates from Sorted Linked List

• Teaching Kids Programming - Remove Duplicates from Sorted Linked List (Using Hash Set)
• Teaching Kids Programming - Remove Duplicates from Sorted Linked List (Two Pointer Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —