(Codewars) Linked Lists - Remove Duplicates

Description

Write a RemoveDuplicates() function which takes a list sorted in increasing order and deletes any duplicate nodes from the list. Ideally, the list should only be traversed once. The head of the resulting list should be returned.

var list = 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 -> null
removeDuplicates(list) === 1 -> 2 -> 3 -> 4 -> 5 -> null


If the passed in list is null/None/nil, simply return null.

Note: Your solution is expected to work on long lists. Recursive solutions may fail due to stack size limitations.

My Solution

class Node(object):
def __init__(self, data, nxt=None):
self.data = data
self.next = nxt

st = set()
while node.next:
if node.next.data in st:
tmp = node.next
node.next = node.next.next
del tmp
else:
node = node.next


I am interested in performance and adhering to best practices.

The space complexity of your solution is $$\O(n)\$$. What if I told you that given the constraints in the question, you could solve this problem in $$\O(1)\$$ space?

Consider that you receive an already sorted list. This implies that all duplicates must be adjacent. This in turn means that for deduplicating these, you do not need to keep track of which values you already encountered.

Note that del is not necessary here. You never use tmp aside from assigning node.next to it in any case. del is not clearing the memory allocated to the variable (or the object it refers to), it only destroys the variable itself, the object is unaffected. As such it does not have any effect on the garbage-collection that python performs...

The following should already work just fine:

def remove_duplicates(head):
while node.next:
if node.next.data == node.data:
node.next = node.next.next
else:
node = node.next


Small sidenote: I really like the hack you used to ensure that you handle the head is None case, but you should be aware that it is just a hack. The cleaner solution to this would be:

def remove_duplicates(head):

• Surely if head is None would be better than if not head, no? It may or may not be faster, depending on where the bottlenecks are (it's usually faster) and it more clearly conveys the intent of the code. – wizzwizz4 Mar 10 '19 at 19:04
• Thanks for this, yours is really neat. It still looks like it's $O(n)$ to me as you have to iterate through the list? – Tobi Alafin Mar 10 '19 at 19:39