# 排序链表
给你链表的头结点 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
```java
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
class Solution {
public ListNode sortList(ListNode head) {
if (head == null)
return head;
return mergeSort(head);
}
public ListNode mergeSort(ListNode head) {
if (head.next == null)
return head;
ListNode p1 = head;
ListNode p2 = head.next;
if (p2 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
ListNode left = head;
ListNode right = p1.next;
p1.next = null;
left = mergeSort(left);
right = mergeSort(right);
return merge(left, right);
}
public ListNode merge(ListNode left, ListNode right) {
ListNode head = null;
if (left.val < right.val) {
head = left;
left = left.next;
} else {
head = right;
right = right.next;
}
ListNode tmp = head;
while (left != null && right != null) {
if (left.val < right.val) {
tmp.next = left;
left = left.next;
} else {
tmp.next = right;
right = right.next;
}
tmp = tmp.next;
}
tmp.next = left != null ? left : right;
return head;
}
}
```
## 答案
```java
```
## 选项
### A
```java
```
### B
```java
```
### C
```java
```