链表快排

链表快排是在面试中比较容易遇到的问题。这里介绍其两种解法。

解法一：

　　基于值的交换法。由于对于链表结点的交换，涉及到指针的操作，比较复杂。所以首先先到不改变结点，而改变结点中的值。

　　通常我们的快排是基于partition的思想进行，通过一次partition，将数组分为两部分，左半部分均小于枢纽元素，右半部分均大于枢纽元素。这个partition的操作，需要两个指针，分别指向头尾。先从尾指针开始操作，找到第一个小于枢纽元素的元素位置，交换头指针元素和当前尾指针元素。之后从头指针往后遍历，找到第一个大于枢纽元素的元素位置，同样和前一步一样做交换操作。那么和数组的处理方式不同的是，链表只支持从前向后遍历。所以这里修改了两个指针的位置，头指针不变，而尾指针指向头指针的下一位，每一次都去判断尾指针所值元素和枢纽元素的大小，当小于枢纽元素时，此时头指针后移一位，和头指针所值结点交换值。尾指针后移。这样的操作保证了头指针及其之前的结点值的大小总是小于等于枢纽元素，而头指针后到尾指针之间的结点值总是大于枢纽值。最后在尾指针遍历到链表最后一个结点时，交换头指针所指结点值和初始的开始位置的结点的值。此时返回的头指针即为partition需要返回的中间值位置。

代码：

 1 struct Node{
 2     int val;
 3     Node* next;
 4     Node(int value){
 5         val = value;
 6         next = nullptr;
 7     }
 8 };
 9 
10 Node* partition(Node* start, Node* end)
11 {
12     Node* slow = start;
13     Node* fast = start->next;
14     int val = start->val;
15     while(fast!=end)
16     {
17         if(fast->val < val)
18         {
19             slow = slow->next;
20             swap(slow->val, fast->val);
21         }
22         fast = fast->next;
23     }
24     swap(slow->val, start->val);
25     return slow;
26 }
27 
28 void qsort(Node* start, Node* end)
29 {
30     if(start!=end)
31     {
32         Node* mid = partition(start, end);
33         qsort(start, mid);
34         qsort(mid->next, end);
35     }
36 }

解法二：

　　在很多面试中，面试官会要求不单纯交换结点值，而是交换链表的结点。这里就涉及了链表指针的操作。

这里的partition，我们选取第一个节点作为枢纽元，然后把小于枢纽的节点放到一个链中，把不小于枢纽的及节点放到另一个链中，最后把两条链以及枢纽连接成一条链。
这里我们需要注意的是：
1.在对一条子链进行partition时，由于节点的顺序都打乱了，所以得保正重新组合成一条新链表时，要和该子链表的前后部分连接起来，因此我们的partition传入三个参数，除了子链表的范围（也是前闭后开区间），还要传入子链表头结点的前驱；
2.partition后链表的头结点可能已经改变

 1 struct Node{
 2     int val;
 3     Node* next;
 4     Node(int value){
 5         val = value;
 6         next = nullptr;
 7     }
 8 };
 9 
10 Node* partition(Node* pre, Node* low, Node* high)
11 {
12     Node node1(0);
13     Node node2(0);
14     int key = low->val;
15     Node* little = &node1;
16     Node* big = &node2;
17     for(Node* i = low; i!=high; i=i->next)
18     {
19         if(i->val < key)
20         {
21             little->next = i;
22             little = little->next;
23         }
24         else
25         {
26             big->next = i;
27             big = big->next;
28         }
29     }
30     big->next = high;
31     little->next = low;
32     low->next = node2.next;
33     pre->next = node1.next;
34     return low;
35 }
36 
37 void qsortlist(Node* prehead, Node* head, Node* tail)
38 {
39     if(head == tail || head->next==tail)
40         return;
41     Node* mid = partition(prehead, head, tail);
42     qsortlist(prehead, head, mid);
43     qsortlist(mid, mid->next, tail);
44 }
45 
46 Node* qsortList(Node* head)
47 {
48     if(head == nullptr || head->next == nullptr)
49         return head;
50     Node tmp (0);
51     tmp.next = head;
52     qsortlist(&tmp, head, NULL);
53     return tmp.next;
54 }