一、链表排序

链表分为单链表和双链表，双链表的排序适合快速排序，这个在c语言库函数中使用sort进行了实现。但是单链表并不适合使用快速排序。因此我们可以使用插入排序、选择排序、冒泡排序等方法。注意：链表不一定会有头结点，但是一定会有一个头指针。特别是如何在不改变原链表指针指向的情况下交换两个节点

1、选择排序

选择排序的思路：选出一个数，假定它是最小/最大值，然后与无序队列中的元素进行比较，直到找出最小值，然后交换数据。

具体做法：重新定义两个链表指针，一个指针指向当前操作的链表节点，取名为p，另一个取名为min，指向本轮排序中数值最小的节点。与数组排序不同的是，数组是记录最小值元素的下标，这里是记录数值最小的节点的指针。

这里需要注意传入的链表是否有头结点，一般有头结点的链表会在创建链表时创建一个头结点（数据域无效或者存储链表节点数）。

2、插入法排序

思路：创建一个有序数列，从原来的无序数列中取出一个数，插入有序数列中。

具体做法：链表中需要创建一个新的链表，用来保存排序好的链表节点。同样的，这里也需要定义一个cur指针，指向原链表当前被操作的节点，sortCur指向有序链表的当前被操作的节点。prev指向当前被操作的节点的前一个节点。与选择法不同的是，这里是新节点插入链表，而不是两个节点的数据交换。