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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.
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.