Teaching Kids Programming – Remove Duplicates from Sorted Linked List (Two Pointer Algorithm)

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 (Two Pointer Algorithm)

As the linked list contains the sorted numbers, we can walk through the linked list and compare the current value and its next one if there is any, delete the next node if the next node is the same as current (duplicate value) by pointing the current.next to current.next.next. The time complexity for this Two Pointer Algorithm to remove duplicates from the given sorted linked list is O(N) and the space complexity is O(1).

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

# 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
        cur = head
        while cur and cur.next:
            if cur.val == cur.next.val:
                tmp = cur.next
                cur.next = cur.next.next
                del tmp
            else:
                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
        cur = head
        while cur and cur.next:
            if cur.val == cur.next.val:
                tmp = cur.next
                cur.next = cur.next.next
                del tmp
            else:
                cur = cur.next
        return head

This could be also solved by using a Hash Set to remember the nodes that we have seen, which can be apply to general case (even when the linked list is not sorted). Also, like many other linked list problems, we can always convert it to array first, process it, and then convert it back to linked list.

We can remove the next node using the del keyword:

1
2
3

node = cur   ## save the node to delete
prev.next = cur.next
del node     ## delete the node

node = cur   ## save the node to delete
prev.next = cur.next
del node     ## delete the node

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) —