Sort a linked list in O(n log n) time using constant space complexity.
题目要求给定时间复杂度对链表进行排序，但是我个人认为题目要求不是很合理，使用归并排序时间复杂度满足要求，但是空间复杂度并不为常数，所以个人认为这道题不严谨，说实话，对链表进行归并排布的代码涉及到递归，我还不是很熟悉，先贴上吧，日后再认真学习：
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 || !head->next)
13 return head;
14 ListNode *fast = head, *slow = head, *pre = head;
15 while (fast && fast->next)
16 {
17 pre = slow;
18 slow = slow->next;
19 fast = fast->next->next;
20 }
21 pre->next = nullptr;
22 return merge(sortList(head), sortList(slow));
23 }
24
25 ListNode *merge(ListNode* l1, ListNode *l2)
26 {
27 ListNode *dummy = new ListNode(-1);
28 ListNode *cur = dummy;
29 while (l1 && l2)
30 {
31 if (l1->val < l2->val)
32 {
33 cur->next = l1;
34 l1 = l1->next;
35 }
36 else
37 {
38 cur->next = l2;
39 l2 = l2->next;
40 }
41 cur = cur->next;
42 }
43 if (l1)
44 cur->next = l1;
45 if (l2)
46 cur->next = l2;
47 return dummy->next;
48 }
49 };