在C中排序链表 [英] Sorting linked lists in C

问题描述

我被要求编写一个需要3个未排序链接列表的函数，并返回一个组合所有三个列表的单个排序链表。你能想到的最好的方式是什么？
我真的没有内存的限制，但是如果没有内存限制，你会做什么？

解决方案

要在所有三个链接列表上使用合并排序，然后使用一个最终合并步骤合并他们一起进入整体排序列表。

与大多数O（n log n）排序算法不同，合并排序可以在链表上高效运行。在高层次上，合并排序的直觉在链表上如下所示：

1. 作为基本情况，如果列表有零或一个元素，它已经被排序。


2. 否则：
   
   
   
   
   1. 将列表分成两个大小相等的列表也许通过将奇数元素移动到一个列表中，甚至将元素移动到另一个列表中。
   
   
   2. 递归地使用合并排序对这些列表进行排序。
   
   
   3. a href =http://en.wikipedia.org/wiki/Merge_algorithm =noreferrer> merge 步骤将这些列表合并成一个排序列表。
   
   

链接列表中的合并算法非常漂亮。伪代码大致如下：

1. 初始化一个包含结果的空链接列表。


2. As只要两个列表都不为空：
   
   
   
   
   1. 如果第一个列表的第一个元素小于第二个列表的第一个元素，请将其移动到
   
   
   2. 否则，将第二个列表的第一个元素移动到结果列表的背面。
   
   



3. 现在只有一个列表为空，将所有元素从第二个列表移动到结果列表的后面。

这可以在O（n）时间内运行，因此合并排序的整体复杂度为O（n log n）。

一次您已经独立排列了所有三个列表，您可以应用合并算法将三个列表合并成一个最终的排序列表。或者，您可以考虑将所有三个链接列表连接在一起，然后使用巨大的合并排序通过同时对所有列表进行排序。没有明确的正确的方式来做到这一点;这真的取决于你。

上述算法运行在&Theta（n log n）时间。它也只使用&（n n）内存，因为它不分配新的链接列表单元，并且只需要每个堆栈帧中的空间来存储各种列表的指针。由于递归深度为&（log n），因此内存使用量为&Theta（log n）。

---

您可以在链接列表中实现的另一个O（n log n）排序是 quicksort 的修改。虽然quicksort的链表版本很快（仍然是O（n log n）），但是它不像在阵列上使用的就地版本那么快，因为数组元素的连续存储缺乏局部性的影响。然而，这是一个非常美丽的算法应用于列表。

quicksort背后的直觉如下：

1. 如果您有零元素或单元素列表，列表将被排序。


2. 否则：
   
   
   
   
   1. 选择列表中的一些要用作枢轴的元素。
   
   
   2. 将列表分为三组 - 小于枢轴的元素，与枢轴相等的元素，以及元素更大
   
   
   3. 递归地排序较小和较大的元素。
   
   
   4. 将三个列表连接成较小，然后相等，然后更大，以返回整体排序列表。
   
   

链表列表版本的一个很好的方面的快速排序是分区步骤比阵列情况下容易得多。选择了一个枢轴（稍后详细介绍）后，您可以通过为小于等于或大于列表创建三个空列表来执行分区步骤，然后对原始链接进行线性扫描列表。然后，您可以将每个链接列表节点附加/添加到与原始存储桶相对应的链接列表。

获得此工作的一个挑战是挑选一个好的枢纽元素。众所周知，如果枢轴的选择不好，快速排序可以退化为O（n ² ），但是也知道如果随机选择一个枢轴元素，运行时是O（n log n）概率很高。在一个数组中这很简单（只是选择一个随机数组索引），但是在链表的情况下是比较棘手的。最简单的方法是选择0和列表长度之间的随机数，然后在O（n）时间内选择该列表的元素。或者，有一些非常酷的方法从链接中随机挑选一个元素; 一个这样的算法在这里描述。

---

如果你想要一个只需要O（1）空间的更简单的算法，你也可以考虑使用插入排序来排序链表。虽然插入排序更容易实现，但它在最坏的情况下运行在O（n ² ）时间（尽管它也具有O（n）最佳情况），所以它可能不是一个好的选择除非你特别想避免合并排序。

插入排序算法背后的想法如下：

1. 初始化一个包含结果的空白链接列表。


2. 对于三个链接列表中的每一个：
   
   
   
   
   1. 虽然该链表不为空：
      
      
      
      
      1. 扫描结果列表以查找此链接列表的第一个元素所在的位置。 / li>
         
      2. 在该位置插入元素。
      
      

   
   

---

可以适应链表的另一个O（n ² ）排序算法是选择排序。这可以非常容易地实现（假设你有一个双向链表）通过使用这个算法：

1. 初始化一个保存结果的空列表


2. 输入列表不为空：
   
   
   
   
   1. 扫描链接列表，寻找最小的剩余元素。
   
   
   2. 从链表中删除该元素。
   
   
   3. 将该元素追加到结果列表。
   
   

这也运行在O（n ² ）时间，只使用O（1）空间，在实践中它比插入排序慢;特别是它总是在&Theta（n ² ）时间运行。

---

根据链接列表的结构如何，您可能可以摆脱一些非常棒的黑客。特别是，如果您被赋予双重链接列表，那么您在每个链接列表单元格中都有两个指针空间。鉴于此，您可以重新解释这些指针的含义，做一些非常荒谬的排序技巧。

作为一个简单的例子，让我们看看如何实现树排序使用链表单元格。这个想法如下。当链表列表单元格存储在链表中时，下一个和前一个指针具有其原始含义。然而，我们的目标是迭代地将链表列表从链表中拉出，然后将它们重新解释为二叉搜索树中的节点a，其中下一个指针意思是右子树，而前一个指针意味着左子树。如果你被允许这样做，这是一个非常酷的实现树排序的方法：

1. 创建一个新的指针链接到列表单元格这将用作指向树根的指针。


2. 对于双向链表的每个元素：
   
   
   
   
   1. 从链表中删除该单元格
   
   
   2. 将该单元格视为BST节点，将该节点插入到二叉搜索树中。
   
   



3. 进行BST的顺序散步。每当您访问节点时，将其从BST中删除并将其插入双向链接列表。

情况O（n log n）时间和最坏情况O（n ² ）。在内存使用方面，前两个步骤只需要O（1）个内存，因为我们从旧的指针中回收空间。最后一步可以在O（1）空间中使用一些特别聪明的算法。

您还可以考虑实现堆排序，虽然这有点棘手。

---

希望这有帮助！

I was asked to write a function that takes 3 unsorted linked lists and return one single sorted linked list that combines all three lists. What is the best way you can think of? I dont really have restrictions of memory but what would you do with/without memory restrictions?

解决方案

One option would be to use merge sort on all three of the linked lists, then use one final merge step to merge them together into an overall sorted list.

Unlike most O(n log n) sorting algorithms, merge sort can run efficiently on linked lists. At a high-level, the intuition behind merge sort on a linked list is as follows:

1. As a base case, if the list has zero or one elements, it's already sorted.
2. Otherwise:
   1. Split the list into two lists of roughly equal size, perhaps by moving odd elements into one list and even elements into the other.
   2. Recursively use merge sort to sort those lists.
   3. Apply a merge step to combine those lists into one sorted list.

The merge algorithm on linked lists is really beautiful. The pseudocode works roughly like this:

1. Initialize an empty linked list holding the result.
2. As long as both lists aren't empty:
   1. If the first element of the first list is less than the first element of the second list, move it to the back of the result list.
   2. Otherwise, move the first element of the second list to the back of the result list.

3. Now that exactly one list is empty, move all the elements from the second list to the back of the result list.

This can be made to run in O(n) time, so the overall complexity of the merge sort is O(n log n).

Once you've sorted all three lists independently, you can apply the merge algorithm to combine the three lists into one final sorted list. Alternatively, you could consider concatenating together all three linked lists, then using a giant merge sort pass to sort all of the lists at the same time. There's no clear "right way" to do this; it's really up to you.

The above algorithm runs in Θ(n log n) time. It also uses only Θ(log n) memory, since it allocates no new linked list cells and just needs space in each stack frame to store pointers to the various lists. Since the recursion depth is Θ(log n), the memory usage is Θ(log n) as well.

---

Another O(n log n) sort that you can implement on linked lists is a modification of quicksort. Although the linked list version of quicksort is fast (still O(n log n) expected), it isn't nearly as fast as the in-place version that works on arrays due to the lack of locality effects from array elements being stored contiguously. However, it's a very beautiful algorithm as applied to lists.

The intuition behind quicksort is as follows:

1. If you have a zero- or one-element list, the list is sorted.
2. Otherwise:
   1. Choose some element of the list to use as a pivot.
   2. Split the list into three groups - elements less than the pivot, elements equal to the pivot, and elements greater than the pivot.
   3. Recursively sort the smaller and greater elements.
   4. Concatenate the three lists as smaller, then equal, then greater to get back the overall sorted list.

One of the nice aspects of the linked-list version of quicksort is that the partitioning step is substantially easier than in the array case. After you've chosen a pivot (details a bit later), you can do the partitioning step by creating three empty lists for the less-than, equal-to, and greater-than lists, then doing a linear scan over the original linked list. You can then append/prepend each linked list node to the linked list corresponding to the original bucket.

The one challenge in getting this working is picking a good pivot element. It's well known that quicksort can degenerate to O(n²) time if the choice of pivot is bad, but it is also known that if you pick a pivot element at random the runtime is O(n log n) with high probability. In an array this is easy (just pick a random array index), but in the linked list case is trickier. The easiest way to do this is to pick a random number between 0 and the length of the list, then choose that element of the list in O(n) time. Alternatively, there are some pretty cool methods for picking an element at random out of a linked list; one such algorithm is described here.

---

If you want a simpler algorithm that needs only O(1) space, you can also consider using insertion sort to sort the linked lists. While insertion sort is easier to implement, it runs in O(n²) time in the worst case (though it also has O(n) best-case behavior), so it's probably not a good choice unless you specifically want to avoid merge sort.

The idea behind the insertion sort algorithm is as follows:

1. Initialize an empty linked list holding the result.
2. For each of the three linked lists:
   1. While that linked list isn't empty:
      1. Scan across the result list to find the location where the first element of this linked list belongs.
      2. Insert the element at that location.

---

Another O(n²) sorting algorithm that can be adapted for linked lists is selection sort. This can be implemented very easily (assuming you have a doubly-linked list) by using this algorithm:

1. Initialize an empty list holding the result.
2. While the input list is not empty:
   1. Scan across the linked list looking for the smallest remaining element.
   2. Remove that element from the linked list.
   3. Append that element to the result list.

This also runs in O(n²) time and uses only O(1) space, but in practice it's slower than insertion sort; in particular, it always runs in Θ(n²) time.

---

Depending on how the linked lists are structured, you might be able to get away with some extremely awesome hacks. In particular, if you are given doubly-linked lists, then you have space for two pointers in each of your linked list cells. Given that, you can reinterpret the meaning of those pointers to do some pretty ridiculous sorting tricks.

As a simple example, let's see how we could implement tree sort using the linked list cells. The idea is as follows. When the linked list cells are stored in a linked list, the next and previous pointers have their original meaning. However, our goal will be to iteratively pull the linked list cells out of the linked list, then reinterpret them as nodes a in binary search tree, where the next pointer means "right subtree" and the previous pointer means "left subtree." If you're allowed to do this, here's a really cool way to implement tree sort:

1. Create a new pointer to a linked list cell that will serve as the pointer to the root of the tree.
2. For each element of the doubly-linked list:
   1. Remove that cell from the linked list.
   2. Treating that cell as a BST node, insert the node into the binary search tree.

3. Do an in-order walk of the BST. Whenever you visit a node, remove it from the BST and insert it back into the doubly-linked list.

This runs in best-case O(n log n) time and worst-case O(n²). In terms of memory usage, the first two steps require only O(1) memory, since we're recycling space from the older pointers. The last step can be done in O(1) space as well using some particularly clever algorithms.

You could also consider implementing heap sort this way as well, though it's a bit tricky.

---

Hope this helps!

这篇关于在C中排序链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！