LeetCode 148 Sort List 链表上的归并排序和快速排序

Sort a linked list in O(n log n) time using constant space complexity.

单链表排序----快排 & 归并排序

（1）归并排序

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* sortList(ListNode* head) {
12         if (head == nullptr || head->next == nullptr)
13             return head;
14         ListNode* slow = head;
15         ListNode* fast = head;
16         ListNode* mid = nullptr;
17         while (fast&&fast->next)
18         {
19             mid = slow;
20             slow = slow->next;
21             fast = fast->next->next;
22         }
23         mid->next = nullptr;
24         return mergeHelp(sortList(head), sortList(slow));
25     }
26     ListNode* mergeHelp(ListNode* low, ListNode* high)
27     {
28         ListNode* head = new ListNode(-1);
29         ListNode* cur = head;
30         while (low&&high)
31         {
32             if (low->val < high->val)
33             {
34                 cur->next = low;
35                 low = low->next;
36             }
37             else
38             {
39                 cur->next = high;
40                 high = high->next;
41             }
42             cur = cur->next;
43         }
44         cur->next = low ? low : high;
45         return head->next;
46     }
47 };

（2）快速排序

①.使第一个节点为中心点；
②.创建2个指针(first，second)，first指向头结点，second指向first的下一个节点；
③.second开始遍历,如果发现second的值比中心点的值小，则此时first=first.next，并且执行当前first的值和second的值交换，second遍历到链表尾即可；
④.把头结点的值和first的值执行交换。此时first节点为中心点,并且完成1轮快排
⑤.使用递归的方法即可完成排序检测是否合法

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* sortList(ListNode* head) {
12         if(head==nullptr)
13             return head;
14         quickSort(head,nullptr);
15         return head;
16     }
17     void quickSort(ListNode* begin,ListNode* end)
18     {
19         if(begin!=end)
20         {
21             ListNode* sep=getSeperator(begin,end);
22             quickSort(begin,sep);
23             quickSort(sep->next,end);
24         }
25     }
26     ListNode* getSeperator(ListNode* begin,ListNode* end)
27     {
28         ListNode* first=begin;
29         ListNode* second=begin->next;
30         int key=begin->val;
31         while(second!=end)
32         {
33             if(second->val<key)
34             {
35                 first=first->next;
36                 swap(first,second);
37             }
38             second=second->next;
39         }
40         swap(begin,first);
41         return first;
42     }
43     void swap(ListNode* a,ListNode* b)
44     {
45         int tmp=a->val;
46         a->val=b->val;
47         b->val=tmp;
48     }
49 };