Remove duplicates from LinkedList

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s