# Remove duplicates from an unsorted Linked List in Ruby

Currently I'm going over the cracking the coding interview. I'm in the Linked List 2.1 question which is as follow:

Remove Duplicates, write code to remove duplicates from an unsorted Linked List. How would you solve the problem if a temporary buffer is not allowed?

I used a Hash, which breaks the temporary buffer not allowed conditioned. Not sure how one can go about solving this without using an extra data structure. The above is the method I used.

# CTCI-2.1: Write code to remove duplicates from an unsorted LinkedList
def remove_duplicates
h = Hash.new(0)
return false unless node.next
while (node = node.next)
h[node.data] += 1
if h[node.data] > 1
previous_node = find_previous(node.data)
previous_node.next = previous_node.next.next
end
end
end


This is a $$\O(n)\$$. How can this be improved? How one will go about solving this without using an additional data structure(Temporary buffer?) Here is the rest of the Linked List: require 'pry'

class Node
attr_accessor :next

def initialize(data)
@data = data
@next = nil
end

def to_s
"Node with value: #{data}"
end
end

def initialize
end

def append(value)
find_tale.next = Node.new(value)
else
end
end

def find_tale

return node if !node.next
return node if !node.next while (node = node.next)
end

def find(value)

return false if !node.next
return node if node.data == value

while (node = node.next)
return node if node.data == value
end
end

def append_after(target, value)
node = find(target)
return unless node

old_next = node.next
node.next = Node.new(value)
node.next.next = old_next
end

def find_previous(value)

return false if !node.next
return node if node.next.data == value

while(node = node.next)
return node if node.next.data == value
end
end

def delete(value)
end

node = find_previous(value)
node.next = node.next.next
end

def display

puts node
while (node = node.next)
puts node
end
end

# CTCI-2.1: Write code to remove duplicates from an unsorted LinkedList
def remove_duplicates
h = Hash.new(0)
return false unless node.next
while (node = node.next)
h[node.data] += 1
if h[node.data] > 1
previous_node = find_previous(node.data)
previous_node.next = previous_node.next.next
end
end
end
end


Here is the test I used:

# TEST

list.append('A')
list.append('B')
list.append('A')
list.append('A')
list.append('C')
list.append('D')

puts "Display the list"

list.display

list.remove_duplicates
puts 'Answer should be A B C D'
list.display

• A minor thing, I would write previous_node.next = previous_node.next.next as previous_node.next = node.next – Marc Rohloff Sep 16 at 16:18

## Alternatives

There are other alternatives (spoiler alert) with around the same time complexity, that adhere to the specification of in-place removal.

## Review

This is in $$\O(n)\$$.

I'm not sure it is. The outer iteration while (node = node.next) is $$\O(n)\$$.

while (node = node.next)
h[node.data] += 1
if h[node.data] > 1
previous_node = find_previous(node.data)
previous_node.next = previous_node.next.next
end
end


And find_previous(data) is $$\O(\log{n})\$$.

 def find_previous(value)

return false if !node.next
return node if node.next.data == value

while(node = node.next)
return node if node.next.data == value
end
end


This makes remove_duplicates to be $$\O(n\log{n})\$$.

If you keep track of the previous node while iterating the nodes, you could optimize your algorithm to be $$\O(n)\$$, but as you are using a hash table, it fails to meet the requirements of the challenge.

• As you point out find_previous is a relatively expensive operation. I would add another local variable to track the previous node. i.e at the top of the function add previous = @head and at the end of the loop previous = node – Marc Rohloff Sep 16 at 16:14
• Looking at that, you should only update previous if you didn't delete the node. – Marc Rohloff Sep 16 at 16:24
• @MarcRohloff that's how I would do it as well. But I'll leave it up to OP to come up with a similar solution :) – dfhwze Sep 16 at 16:27
• would using merge sort violate the no extra buffer condition? I think merge sort uses two arrays but not sure if their created in memory – Steven Aguilar Sep 27 at 15:12
• I believe it would breach that condition: geeksforgeeks.org/merge-sort. – dfhwze Sep 27 at 15:14