[Solved] What is the optimal solution to reversing: append doubled list and randomizing?

JYCT Asks: What is the optimal solution to reversing: append doubled list and randomizing?
I am looking at this challenge:

A function takes a list of numbers, extends that list with the doubles of those numbers and then shuffles the result randomly.

Example:

Code:
 [1,2,4] > [1,2,4,2,4,8] > [8,4,1,2,2,4]

Write a function that takes a potential output list and returns the original list. Return none if no such possible original list exists.

Examples​

Code:
[8,4,1,2,2,4] > [1,2,4]

[1,4,2] > None

I can see an O(nlogn) solution by sorting and then using a hashmap to keep track of doubles to skip every time you come across a new original number.

Is there a faster solution (perhaps linear)?

Ten-tools.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your response here to help other visitors like you. Thank you, Ten-tools.