快排很简单，就是右左两边来回摇摆。但存储结构选为链表还是有一定麻烦的。
不过有一种取巧的方法，就是保持链表结构不变，只改变链表节点所包含的值（next不变，val改变），这就和数组差不多了。
不过写链表快排的目的就是为了熟悉链表操作，毕竟实际应用中不会有这样的需求。因此取巧是我辈不屑的，自然是怎么复杂怎么来：）
下面给出的是改变链表结构的快速排序。
先简单介绍思想：
快排思想很简单，先根据头结点，把数据划分成两块，然后继续递归，直至剩下一个数据。
用链表实现的难点在于如何在排序中保持链表结构的连续性。
因为划分的过程中会改变链表结构。递归调用也会改变链表结构。而无论Java或C++传递的引用（指针）形参都是按值传递的（指针的拷贝或引用的拷贝），
在函数中改变对象固然会引起原对象的改变，可只改变引用本身，原引用却不会变化。
如何保证头结点的不变性就成了关键所在。下面分别予以说明：
Partition：
在partition中我们传递一个哑结点，在划分过程中这个节点不会改变，我们把小于pivot的节点插到head前面，使其成为新的head，
直至最后划分完成，返回pivot节点。如果不设置哑节点，我们就无法把新head节点传递出去，毕竟引用是按值传递的。函数外面的head始终
指向最初的头结点。也许C++中可以用指针的指针来解决这一的，但Java中我们却无能为力。因此，引入一个不变的dummyNode，通过改变dummyNode.next
的值，来传递头结点。这是可以的，因为对象是按引用传递的：） 只要dummyNode不变，dummyNode.next就始终指向头结点。
QuickSort:
quickSort中也有可能改变链表结构，因为quickSort会递归调用partition。碍于接口限制，我们必须传递真实的头结点。
但好消息是，我们不需要返回pivot了，因此我们可以靠返回值来更新头结点。
肯定有人会问，尾节点怎么办呢？
在数组快排中我们递归是闭区间，也就是说[first，pivotIndex-1],[pivotIndex+1 ,last],但链表快排却不能这样。
一方面是因为单链表找上个节点复杂度太高，另一方面这样做我们还要处理尾节点的改变问题，这是不能接受的。因此我们这里将其改为
前闭后开区间[head, tail)，也就是说始终保持尾节点不变。
public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }
public ListNode QuickSort(ListNode head,ListNode tail) { //add dummyNode to asure the head not changed in partition ListNode dummyNode = new ListNode(0); dummyNode.next =head; if (head != tail && head.next != tail) { ListNode pivot = partition(dummyNode, tail); dummyNode.next = QuickSort(dummyNode.next, pivot); //dummyNode.next is head, which is a copy of inference. It has to be updated to prevent the link broken pivot.next = QuickSort(pivot.next, tail); //pivot.next has to be updated too for the same reason. } return dummyNode.next; } public ListNode partition(ListNode dummyNode, ListNode tail) { ListNode start = dummyNode.next; ListNode end = tail; ListNode pNode = start; while (start != end) { while (start.next != null && start.next.val >= pNode.val) { start = start.next; } if (start.next == null) { return pNode; }
ListNode qNode = start.next; start.next = start.next.next; qNode.next = dummyNode.next; dummyNode.next = qNode; } return pNode; }
public static void main(String [] args)
{
//there is a Linked list, head is its head node.
QuickSort(head,null)
}