# 排序链表
给你链表的头结点 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
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if head == None:
return None
else:
return self.mergeSort(head)
def mergeSort(self, head):
if head.next == None:
return head
fast = head
slow = head
pre = None
while fast != None and fast.next != None:
pre = slow
slow = slow.next
fast = fast.next.next
pre.next = None
left = self.mergeSort(head)
right = self.mergeSort(slow)
return self.merge(left, right)
def merge(self, left, right):
tempHead = ListNode(0)
cur = tempHead
while left != None and right != None:
if left.val <= right.val:
cur.next = left
cur = cur.next
left = left.next
else:
cur.next = right
cur = cur.next
right = right.next
if left != None:
cur.next = left
if right != None:
cur.next = right
return tempHead.next
```
## 答案
```python
```
## 选项
### A
```python
```
### B
```python
```
### C
```python
```