Question:

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.

Concept:

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

### Like this:

Like Loading...