本节书摘来自华章计算机《算法基础》一书中的第3章，第3.5节，作者：（美）罗德·斯蒂芬斯（Rod Stephens）著，更多章节内容可以访问云栖社区“华章计算机”公众号查看
3.5 链表算法
到目前为止，本章描述了一些用于建立和维护链表的算法，包括在链表的开头、结尾和中间添加项的算法，查找链表中项的算法和从链表中删除项的算法。
以下各节描述了利用其他方式来操作链表的算法。
3.5.1 复制链表
一些算法重新排列链表。本节和下一节将描述一些对链表中的项进行排序的算法。如果想保持原来链表的顺序，就必须在排序之前就做一个该链表的副本。
下面的伪代码演示了如何复制一个单链表：
该算法相当简单，但有一点值得一提：该算法使用last_added来跟踪最新被加入到链表副本中的单元格。当要把一个项插入到链表中时，该算法将last_added.Next指向一个新的单元格对象。这使新的对象在该链表的末尾。然后该算法更新last_added以指向新单元格并将原始单元格的值赋予它。
这允许链表从底部而不是从顶部增长。如果如同3.10节“练习1”中的所描述的那样：跟踪链表的最后一个项，类似于如何轻松地将项添加到链表的末尾。
3.5.2 链表的插入排序
在第6章中谈到了许多关于排序的算法，但是其中有两种算法值得在这里进行讨论：选择排序（我们将在下一节中进行描述）和插入排序。
排序算法的基本思想是把一个单元格从待输入链表中提取出来，并将其插入到一个已经排好序的链表（其最初开始是空的）中的适当位置。
下面的伪代码展示了插入排序算法，这里的待排序的各个单元格被存储在一个具有top哨兵的单向链表中：
该算法开始通过建立一个空的链表来保存排序的输出。然后，它从一个无序的输入链表的头至尾进行循环。对于每个输入单元格，算法遍历前面已经排好序的链表来找到一个新单元格对应的位置。然后，它把新单元格插入。
如果调用之前的3.2.6节中描述的插入单元格算法InsetCell，可以简化代码。
如果输入链表中的单元格已经按照从大到小的顺序排列好，该算法只需用短短的几个步骤就可以实现从链表开头插入一个新单元格。如果链表保存N个单元格，在新的链表中插入的所有项总共需要O(N)的步骤。这是该算法的最佳情况。
如果在输入链表中单元格已经从小到大排序，这种算法必须从新的链表的末尾插入每个单元格。而对于每次插入一个链表都需要查找已有链表的末尾单元格。因此，插入所有项需要1＋2＋3＋…＋N＝N×(N＋1)÷2＝O(N2)的步骤。
在平均情况下，要插入的项是随机排列的，该算法可以快速插入一些项，但其他项需要更长的时间。其结果是，该算法的运行时间仍然是O(N2)，虽然实际上它不会需要最坏情况所需的时间。许多其他的排序算法只需要O(N log N)的时间，而这种算法的时间复杂度为O(N2)，表现则相对缓慢。这使得该算法面对数据量较大的链表表现无力。然而，它在数据量较小的链表中运行很快，并且它适用于链表，许多其他的算法并不适用于链表。
