深入单链表的快速排序详解

单链表的快排序和数组的快排序基本思想相同，同样是基于划分，但是又有很大的不同：单链表不支持基于下标的访问。故书中把待排序的链表拆分为2个子链表。为了简单起见，选择链表的第一个节点作为基准，然后进行比较，比基准小得节点放入左面的子链表，比基准大的放入右边的子链表。在对待排序链表扫描一遍之后，左边子链表的节点值都小于基准的值，右边子链表的值都大于基准的值，然后把基准插入到链表中，并作为连接两个子链表的桥梁。然后分别对左、右两个子链表进行递归快速排序，以提高性能。
但是，由于单链表不能像数组那样随机存储，和数组的快排序相比较，还是有一些需要注意的细节：

1、支点的选取，由于不能随机访问第K个元素，因此每次选择支点时可以取待排序那部分链表的头指针。
2、遍历量表方式，由于不能从单链表的末尾向前遍历，因此使用两个指针分别向前向后遍历的策略实效，
事实上，可以可以采用一趟遍历的方式将较小的元素放到单链表的左边。具体方法为：
1)定义两个指针pslow，pfast，其中pslow指向单链表的头结点，pfast指向单链表头结点的下一个结点;
2)使用pfast遍历单链表，每遇到一个比支点小的元素，就令pslow=pslow->next，然后和pslow进行数据交换。
3、交换数据方式，直接交换链表数据指针指向的部分，不必交换链表节点本身。
基于上述思想的单链表快速排序实现如下：
 head