Sorting a linked list and returning to original unsorted order

I have an unsorted linked list. I need to sort it by a certain field t开发者_运维百科hen return the linked list to its previous unsorted condition. How can I do this without making a copy of the list?

When you say "return the linked list to its previous unsorted condition", do you mean the list needs to be placed into a random order or to the exact same order that you started with?

In any case, don't forget that a list can be linked into more than one list at a time. If you have two sets of "next"/"previous" pointers, then you can effectively have the same set of items sorted two different ways at the same time.

To do this you will need to either sort and then restore the list or create and sort references to the list.

To sort the list directly Merge Sort is most likely the best thing you could use for the initial sort, but returning them to their original state is tricky unless you either record your moves so you can reverse them or store their original position and resort them using that as the key.

If you would rather sort the references to the list instead you will need to allocate enough space to hold pointers to each node and sort that. If you use a flat array to store the pointers then you could use the standard C qsort to do this.

If this is an assignment and you must implement your own sort then if you don't already know the length of the list you could take advantage of having to traverse it to count its length to also choose a good initial pivot point for quicksort or if you choose not to use quicksort you can let your imagination go wild with all kinds of optimizations.

Taking your points in reverse order, to support returning to original order, you can add an extra int field to each list node. Set those values based on the original order, and when you need to return it to the original order, just sort on that field.

As far as the sorting in general goes, you probably want to use something like a merge-sort or possibly a Quick-sort.

You can make that data structure somewhat like this.

struct Elem {
 Elem* _next;
 Elem* _nextSorted;
 ...
}

Then you can use any algo for sorting the list (maybe merge sort)

If you want to keep your linked list untouched, you should add information to store the ordered list of elements.

To do so, you can either create a new linked list where each element points to one element of your original linked list. Or you can add one more field in the element of your list like sorted_next.

In any case, you should use a sequential algorithm like mergesort to sort a linked list.

Here is a C source code of mergesort for linked lists that you could reuse for your project.

I guess most of the answers have already covered the usual techniques one could use. As far as figuring out the solution to the problem goes, a trick is to look at the problem and think if the human mind can do it.

Figuring out the original random sequence from a sorted sequence is theoretically impossible unless you use some other means. This can be done by

a)modifying the linked list structure (as mentioned above, you simply add a pointer for the sorted sequence separately). This would work and maybe technically you are not creating a separate linked list, but it is as good as a new linked list - one made of pointers.

b)the other way is to log each transition of the sorting algo in a stack. This allows you to not be dependent on the sorting algorithm you use. For example when say node 1 is shifted to the 3rd position, you could have something like 1:3 pushed to the stack. The notation, of course, may vary. Once you push all the transitions, you can simply pop the stack to give take it back to the original pattern / any point in between. This is more like

If you're interested in learning more about the design for loggers, I suggest you read about the Command Pattern