Given a sorted linked list, delete all duplicates such that each element appear only once.
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
Keep track of all elements that have already been visited (using set) and maintain previous node pointer while moving forward in the list.
Only if the current node value is new, set prev_node.next = current_node.(And update prev node, current_node).
Otherwise don’t connect prev node to the current node (and update the current_node = current_node.next).
And in the end, set prev_node.next = None.
''' Given a sorted linked list, delete all duplicates such that each element appear only once. For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3. ''' def remove_dups(head): my_set = set() prev = None while head: if head.val not in my_set: if prev != None: prev.next = head my_set.add(head.val) prev = head head = head.next prev.next = None import scratch_pad a = scratch_pad.a remove_dups(a) scratch_pad.print_list(a)
But we didn’t use the property that the list is already sorted. Can we use this information to optimize our code further?
Yes, instead of using set(), we can use a variable and keep moving forward untill a different value is reached and then connect both nodes.
Here is the improved code:
def remove_dups_without_space(head): prev = None current_node = head while current_node: if prev != None: while current_node != None and prev.val == current_node.val: current_node = current_node.next if prev: prev.next = current_node if current_node: prev = current_node current_node = current_node.next