# 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
- 你可以在
O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
- 链表中节点的数目在范围
[0, 5 * 104] 内
-105 <= Node.val <= 105
## template
```cpp
#include
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
ListNode *sortList(ListNode *head)
{
return mergesort(head);
}
ListNode *mergesort(ListNode *node)
{
if (!node || !node->next)
return node;
ListNode *fast = node;
ListNode *slow = node;
ListNode *brek = node;
while (fast && fast->next)
{
fast = fast->next->next;
brek = slow;
slow = slow->next;
}
brek->next = nullptr;
ListNode *l1 = mergesort(node);
ListNode *l2 = mergesort(slow);
return merge(l1, l2);
}
ListNode *merge(ListNode *l1, ListNode *l2)
{
if (l1 == NULL)
{
return l2;
}
if (l2 == NULL)
{
return l1;
}
if (l1->val < l2->val)
{
l1->next = merge(l1->next, l2);
return l1;
}
else
{
l2->next = merge(l2->next, l1);
return l2;
}
}
};
```
## 答案
```cpp
```
## 选项
### A
```cpp
```
### B
```cpp
```
### C
```cpp
```