对链表进行排序并返回到原始未排序的顺序
我有一个未排序的链表。我需要按某个字段对其进行排序，然后将链接列表返回到之前的未排序状态。如何在不复制列表的情况下执行此操作？
I have an unsorted linked list. I need to sort it by a certain field then return the linked list to its previous unsorted condition. How can I do this without making a copy of the list?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
当您说“将链表返回到之前的未排序条件”时，您的意思是该列表需要按随机顺序放置还是与开始时完全相同的顺序？
无论如何，不要忘记一个列表一次可以链接到多个列表。如果您有两组“下一个”/“上一个”指针，那么您可以有效地同时以两种不同的方式对同一组项目进行排序。
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.
为此，您需要对列表进行排序然后恢复，或者创建对列表的引用并对其进行排序。
直接对列表进行排序合并排序很可能是您可以用于初始排序的最佳方法，但是将它们返回到原始状态是很棘手的，除非您记录您的移动以便可以反转它们或存储它们的原始位置并使用它们重新排序那个作为关键。
如果您想对列表的引用进行排序，则需要分配足够的空间来保存指向每个节点的指针并对其进行排序。如果您使用平面数组来存储指针，那么您可以使用标准 C qsort 来执行此操作。
如果这是一项作业并且您必须实现自己的排序，那么如果您还不知道列表的长度，您可以利用必须遍历它来计算其长度的优势，以便为快速排序选择一个好的初始枢轴点，或者如果如果你选择不使用快速排序，你可以尽情发挥你的想象力，进行各种优化。
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
qsortto 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.
以相反的顺序获取点，为了支持返回原始顺序，您可以向每个列表节点添加一个额外的
int字段。根据原始顺序设置这些值，当您需要将其返回到原始顺序时，只需对该字段进行排序即可。就一般排序而言，您可能想要使用类似 merge 的东西-sort 或可能是快速排序。
Taking your points in reverse order, to support returning to original order, you can add an extra
intfield 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.
您可以使该数据结构有点像这样。
然后您可以使用任何算法对列表进行排序（也许 合并排序< /a>)
You can make that data structure somewhat like this.
Then you can use any algo for sorting the list (maybe merge sort)
如果您想让链接列表保持不变，则应该添加信息来存储有序的元素列表。
为此，您可以创建一个新的链表，其中每个元素都指向原始链表的一个元素。或者，您可以在列表元素中再添加一个字段，例如sorted_next。
无论如何，您应该使用像归并排序这样的顺序算法来对链表进行排序。
这是链表的 C 源代码的归并排序您可以在您的项目中重复使用。
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.
我想大多数答案已经涵盖了人们可以使用的常用技术。就找出问题的解决方案而言，一个技巧是审视问题并思考人类思维是否可以做到。
从排序序列中找出原始随机序列理论上是不可能的，除非使用其他方法。这可以通过
a）修改链表结构来完成（如上所述，您只需单独为排序序列添加一个指针）。这可行，也许从技术上讲，您没有创建一个单独的链表，但它与一个新的链表一样好——一个由指针组成的链表。
b）另一种方法是将排序算法的每次转换记录在堆栈中。这使您可以不依赖于您使用的排序算法。例如，当节点 1 移动到第三个位置时，您可以将 1:3 之类的内容推送到堆栈中。当然，符号可能会有所不同。一旦你推送了所有的转换，你可以简单地弹出堆栈，将其恢复到原始模式/之间的任何点。这更像是
如果您有兴趣了解有关记录器设计的更多信息，我建议您阅读命令模式< /a>
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