0
$\begingroup$

Is there an algorithm I could use when copying the values is not allowed? My list is going to be sorted in an ascending order.

Also can this be done in a quadratic time?

I will be attempting this in Python.

$\endgroup$
0
$\begingroup$

Copy the list into an array, sort the array, construct a linked list from it. Done. It suffices to populate the array with pointers (references) to the values; you don't need to copy the values themselves. The running time will be $\Theta(n \log n)$ if you use an appropriate sorting algorithm -- much faster than quadratic time.

$\endgroup$
  • $\begingroup$ Without copying its value means that u cant even copy to an array $\endgroup$ – Turing101 Nov 25 '19 at 3:45
  • $\begingroup$ You only copy pointers, not values. Funny enough, I had that as an interview question once. Even for sorting arrays it would be useful if copying values is much more expensive than comparing, because it lets you get away with O(n) copy operations. $\endgroup$ – gnasher729 Nov 25 '19 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.