I am working on some sorting tasks with lists and I was able to implement a solution but my solution takes too long.
Execution timed out after 5000ms....
Here are the details of the task:
- List with n+1 Elements
- Output should be like this
My approach was simply to create a new list, start from the tail and the head of the old list add each element in the new list and go next to tail+1 and head-1 until all elements are transferred.
As mentioned before, the program works but the approach takes to long.
Does anybody have a better idea to speed up the process?
Don't call that sorting beause you are not using any features of the values to order your new list. Call it reordering because you are using some feature of the original list to reate the ordering of the new list. If you are using → operators and saying, “tail,” or, “head,” that would suggest to me that you are using linked lists. Did you really mean, “tail + 1,” or, “head − 1”? Surely it should read, “tail − 1,” or, “head + 1”? I presume you have a doubly‑linked list so you can call previous() on a node. I presume you are not using a get() method, which is notoriously slow on linked lists.
As Norm and Stephan imply, that general approach sounds correct.
If you have a singly‑linked list, create a linked list to use as a stack, add alternate nodes to the stack or to an ordinary list, then iterate the stack and intermediate list and interleave the nodes into your final list. Remember that a stack returns its contents in reverse insertion order.
Piet Souris wrote:. . . you can certainly do sorting here. . . .
Yes, of course you can sort the list, but that doesn't seem to be what the OP requires. It says here that sorting a linked list in situ tends to run in n²logn complexity. If you are using the method in that link, wouldn't the sort run in nlogn complexity?