给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
输入：head = [4,2,1,3]
输出：[1,2,3,4]
class Solution {
public ListNode sortList(ListNode head) {
if (head == null) {
return null;
}
ListNode temp = head;
int length = 0;
while (temp != null) {
length++;
temp = temp.next;
}
ListNode dummyNode = new ListNode(0, head);
for (int subLength = 1; subLength < length; subLength *= 2) {
ListNode pre = dummyNode;
ListNode cur = dummyNode.next;
while (cur != null) {
ListNode head1 = cur;
for (int i = 1; i < subLength && cur.next != null; i++) {
cur = cur.next;
}
ListNode head2 = cur.next;
cur.next = null;
cur = head2;
for (int i = 1; i < subLength && cur != null && cur.next != null; i++) {
cur = cur.next;
}
ListNode next = null;
if (cur != null) {
next = cur.next;
cur.next = null;
}
ListNode merged = merge(head1, head2);
pre.next = merged;
while (pre.next != null) {
pre = pre.next;
}
cur = next;
}
}
return dummyNode.next;
}
public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummyHead = new ListNode(0);
ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 != null) {
temp.next = temp1;
} else if (temp2 != null) {
temp.next = temp2;
}
return dummyHead.next;
}
}