Remove Duplicated from Sorted List II
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
Approach1: Two pass - Dictionary
My first thought upon reading this problem is to use a dictionary to solve it. We would first do a first pass through which the dictionary would store the frequency of each value of the Linked List. Having stored the frequencies, we execute a second pass so we can now delete each values for which their count in the dictionary is greater than 1 hence a duplicate.
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
dummy = curr = ListNode(None)
dummy.next = head
curr = curr.next
count = {}
while curr:
count[curr.val] = count.get(curr.val, 0) + 1
curr = curr.next
curr = dummy
while curr.next:
if count[curr.next.val] > 1:
curr.next = curr.next.next
else:
curr = curr.next
return dummy.next
Time: O(n) Space: O(n)
Approach2: One Pass (optimal)
Although the above code works perfectly, we know that considering that the Linked List is sorted, we should be able to avoid utilizing any additional additional data structures that are ramping up our space complexity. After profound reflection (not really, got the hint :) ), we should be able to get O(1) space by applying this fundamental concept.
Iterate through the Linked List with a curr pointer pointer followed by a prev pointer. When the curr pointer encounters an element that is equal to it's current value. Curr pointer runs until it's next element does not equal to it's current value. Once that occurs, prev pointer's -> next then prints at curr's -> next thereby deleting all elements that were duplicates. As often with Linked List's, we return dummy->next.
# 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: ListNode) -> ListNode:
if not head or not head.next: return head
dummy = prev = curr = ListNode(None)
dummy.next = head
while curr and curr.next:
if curr.val == curr.next.val:
while curr.next and curr.val == curr.next.val:
curr = curr.next
prev.next = curr.next
curr = prev.next
else:
prev = curr
curr = curr.next
return dummy.next
Last updated
Was this helpful?