题目：排序链表
解法一：归并排序（分治）
时间复杂度：O(nlogn)，空间复杂度：O(logn)
从上至下将链表拆分为长度为一的单链表，然后先对长度为1的链表排序，合并两个链表；
再对长度为2的两个链表排序，之后合并….以此类推，每次排序并合并一半链表，最终就可以得到有序的链表
具体实现：
mergeSort（）：
在头部定义一个哨兵节点，然后遍历比较left与right的值，如果left更小，就将当前left节点接到哨兵节点后面，并将left向后移动一位，继续比较（right同理）；最后当left或者right其中一个为空，也就是该子链表遍历完成时，就直接将另一个链表接到末尾，此时返回的哨兵节点的next就是排序后的链表的头节点
sortList（）： 在主函数中，需要不断地将链表分为两半（通过递归调用），之后每一层递归都会调用mergeSort函数对当前分割出来的两个链表进行排序，直到最后合成回初始的链表
解法二：归并排序（迭代）
ps：这里我还没看明白，之后再补上………………..
1class Solution
2{
3public:
4 ListNode* mergeSort(ListNode* left, ListNode* right)
5 {
6 ListNode* dummyNode = new ListNode(0);
7 ListNode* trail = dummyNode;
8 while(left && right)
9 {
10 if(left->val < right->val)
11 {
12 trail->next = left;
13 left = left->next;
14 }
15 else
16 {
17 trail->next = right;
18 right = right->next;
19 }
20 trail = trail->next;
21 }
22 if(left)
23 trail->next = left;
24 else
25 trail->next = right;
26
27 return dummyNode->next;
28 }
29
30 ListNode* sortList(ListNode* head)
31 {
32 if(!head || !head->next) return head;
33
34 ListNode *slow = head, *fast = head->next;
35 while(fast && fast->next)
36 {
37 slow = slow->next;
38 fast = fast->next->next;
39 }
40 ListNode *second = slow->next;
41 slow->next = nullptr;
42 ListNode *first = head;
43
44 first = sortList(first);
45 second = sortList(second);
46
47 return mergeSort(first, second);
48 }
49};