###QuickSort on Singly Linked List
#####Rationale
- 思路和数据的快速排序一样，都需要找到一个pivot元素、或者节点。然后将数组或者单向链表划分为两个部分，然后递归分别快排。
- 针对数组进行快排的时候，交换交换不同位置的数值，在分而治之完成之后，数据就是排序好的。那么单向链表是什么样的情况呢？除了交换节点值之外，是否有其他更好的方法呢？可以修改指针，不进行数值交换。这可以获取更高的效率。
- 在修改指针的过程中，会产生新的头指针以及尾指针，要记录下来。在partition之后，要将小于pivot的的部分、pivot、以及大于pivot的部分重新串起来成为一个singly linked list。
#####Choose pivot
- choose the first node or the last node
- choose a random node -> average: O(NlogN) worst: O(N^2) generate a random num less than the length of singly linked list, and choose that node as pivot
- choose the median node -> worst: O(NlogN) Median of median selection algorithm to choose the median node.
####Implementation
// choose the last node as the pivot
public ListNode quickSortRecur(ListNode head, ListNode tail) {
if (head == tail) return head;
ListNode pivot = tail, cur = head, pre = null, newhead = null;
while(pivot != cur) {
if(cur.val < pivot.val) {
if (null == newhead) newhead = cur;
pre = cur;
cur = cur.next;
} else {
tail.next = cur;
tail = tail.next;
ListNode tmp = cur.next;
cur.next = null;
cur = tmp;
if (null != pre) {
pre.next = cur;
}
}
}
if (pre != null) {
newhead = quickSortRecur(newhead, pre);
ListNode tmp = newhead;
while(pivot != tmp.next) tmp = tmp.next;
tmp.next = pivot;
}else {
newhead = pivot;
}
if (pivot != tail)
pivot.next = quickSortRecur(pivot.next, tail);
return newhead;
}