下午面了momenta，单链表快排没答出来，是自己能力不够，正好可以查漏。
思路：利用节点值域的交换，主要思想还是partiiton，将链表分隔成左右两部分，按照头结点的data(即为tag)，左边的data都小于tag，右边的data都大于tag
node* partition(node* &head, node* end) { //链表为空或者head == end 为递归出口 if (!head || head == end) return head; //p在前 q在后 node* p = head; int tag = head->data; node* q = head->next; while (q != end) { if (q->data < tag) { //此时p q相邻 if (p->next == p) { int t = p->data; p->data = q->data; q->data = t; } //此时p q不相邻 始终保证p->data = tag else { int t = p->data; p->data = q->data; q->data = p->next->data; p->next->data = tag; } p = p->next; q = q->next; } else { q = q->next; } } return p; } void quickSortOfLinkList(node* &head, node* end) { //链表为空或者只有一个节点 if (!head || head == end) return; node* p = partition(head, end); quickSortOfLinkList(head, p); quickSortOfLinkList(p->next, end); }