DEV Community

Shirley
Shirley

Posted on

Remove Duplicates From Linked List - Cracking the Coding Interview, Leetcode

This problem appears in both Cracking the Cracking Interview and Leetcode. The problem is this: given a linked list, delete duplicates such that each number appears only once.

For example:

input: 1 -> 1 -> 2
output: 1 -> 2
Enter fullscreen mode Exit fullscreen mode

Here's a hint. Use a hashset to store your unique numbers in, and if the number exists already in the hashset, set the pointer of the previous node equal to the next node of current node.

class Node:
  self.data = data
  self.next = None

class Solution:
  def removeDuplicates(self, head:Node) -> Node:
      hashSet = set()
      node = head
      prev = None
      while node:
         if node.data not in hashSet:
            hashSet.add(node.data)
            prev = node
         else:
            prev.next = node.next
          node = node.next
      return head
Enter fullscreen mode Exit fullscreen mode

Top comments (9)

Collapse
 
srleyva profile image
Stephen Leyva (He/Him)

Apologies as I’m usually really bad at these Leetcode challenges, but where is traversal of the linked list happening? Is the while loop implicitly setting node equal to node.next? Thanks for the article! Always great to have these solution in the tool box!

Collapse
 
xshirl profile image
Shirley

Oops, I forgot a line! Thanks for noticing! Traversal happens when node = node.next, after the if and else statements! Sorry for forgetting haha.

Collapse
 
srleyva profile image
Stephen Leyva (He/Him)

Aww! Great! I was like another magical python thing 😂😂😂 once again thanks for the article!

Collapse
 
darkwiiplayer profile image
𒎏Wii 🏳️‍⚧️ • Edited

The interesting question would be how to solve that problem without using a hashset.


EDIT: To clarify, the original question really just tests for knowledge: Do you know what a hash-set is and can you identify its benefits in a very simple example. Removing the hashset from the toolbox suddenly confronts you with a more uncomfortable situation where there is no clear answer. By removing the "universal" right answer, you need more information, so this tests communication skills, intuition for spotting problematic edge-cases, etc.

Collapse
 
emindeniz99 profile image
Emin Deniz

Map, set or array can be used. But when using array we must insert and search efficiently like Set to minimize the complexity.
My idea is start from head and go to tail. When processing nodes, put some a list and
for each next node, search that it is exist or not in this list, if exists delete current node from list. Else insert this to list.

Collapse
 
darkwiiplayer profile image
𒎏Wii 🏳️‍⚧️

Map, set or array can be used.

A set can be implemented as a map to boolean values, so that should be forbidden as well, otherwise the question doesn't become more interesting.

The array solution is where things become complicated: If you have a very long list of few numbers (say 10 million numbers all between 1 and 1000), you could allocate an array of 1000 boolean values to serve as an improvised int to bool map.

Another followup question could then be "How can we optimize that solution for memory and what would be the downsides of this?" and you've now covered everything from very high-level concepts to bit-level optimization techniques without doing anything too difficult or specific.

However, if it's a list of 100 numbers of any size that fits a 64bit integer, saving them in a sorted list for binary search would be a good solution.

Collapse
 
codinglanguages profile image
Your DevOps Guy

I'd recommend adding some space and time analysis to the article since you can expect questions about this during your interviews.

Also, how would you solve it without a hash set? There's an obvious brute force solution with O(n^2) time complexity and O(1) space complexity.

PS: I liked your clean code!

Collapse
 
habibcseju profile image
Habib

Can anyone give me leetcode link of this problem ?

Collapse
 
habibcseju profile image
Habib