148. 排序链表
O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序
思路
此题为链表的归并排序
1 使用快慢指针法找到链表的中间节点
2 然后断开链表，两个链表分别递归排序
3 将两个有序的链表归并成一个有序链表
代码
class Solution {
//归并排序
public ListNode sortList(ListNode head) {
if (head == null || head.next == null){
return head;
}
ListNode sentinal = new ListNode(0, head);
ListNode p1 = sentinal;
ListNode p2 = sentinal;
while (p2 != null && p2.next != null){
p1 = p1.next;
p2 = p2.next.next;
}
//p1为中间节点
p2 = p1.next;
p1.next = null;
//两边递归再归并
ListNode cur1 = sortList(head);
ListNode cur2 = sortList(p2);
ListNode nxt1 = cur1.next;
ListNode nxt2 = cur2.next;
sentinal.next = null;
ListNode newTail = sentinal;
while (cur1 != null && cur2 != null){
if(cur1.val <= cur2.val){
newTail.next = cur1;
cur1 = nxt1;
if (nxt1 != null) {
nxt1 = nxt1.next;
}
}else {
newTail.next = cur2;
cur2 = nxt2;
if (nxt2 != null){
nxt2 = nxt2.next;
}
}
newTail = newTail.next;
}
if (cur1 != null){
newTail.next = cur1;
}
if (cur2 != null){
newTail.next = cur2;
}
return sentinal.next;
}
}