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$
1
$\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.

| cite | improve this answer | |
$\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
1
$\begingroup$

Quicksort and mergesort can both be implemented to work directly on a linked list with just $O(1)$ extra space. This actually improves the space complexity of the usual mergesort, which ordinarily requires $O(n)$ working space (this is because the pointers actually constitute $O(n)$ extra space themselves). As usual, mergesort will take $O(n\log n)$ time in the worst case, while quicksort has an $O(n^2)$ worst-case time but is $O(n\log n)$ on "most" inputs.

For quicksort, on each subproblem you can walk the list to find a suitable pivot without hurting the asymptotic complexity. Each partition step consists of simply growing 2 lists, those < the pivot and those >= it. Then append the pivot to the end of the first list, and the second list to that.

For mergesort, to find the halfway point of a singly linked list, walk 2 pointers forward, with one (the "hare") advancing twice at each step and the other (the "tortoise") only once. Once the hare reaches the end, the tortoise is halfway. Now you can merge the two half-length sublists that begin at the start of the original list, and at the tortoise.

Insertion sort can also be straightforwardly implemented to run directly on a linked list, but this is probably a bad choice as its performance will be $O(n^2)$ unless the list is already nearly reverse-sorted (note the difference to the array version in which insertion sort is fast on nearly sorted inputs). This is because the intermediate solution gets built by taking the next element and appending it to the front of the result, meaning it gets built in reverse order.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

If you really, really want no extra space, you can do bubble sort. Normally bubble sort works on an array, starts at the first item, proceeds to the last item and exchanges consecutive items. You can do all this with a linked list.

| cite | improve this answer | |
$\endgroup$

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.