• ㊗️
• 大家
• offer
• 多多！

## Problem

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

Output: [1,2,3,4]

Example 2:

Output: [-1,0,3,4,5]

Example 3:

Output: []

Constraints:

• The number of nodes in the list is in the range $[0, 5 * 10^4]$.
• $-10^5 <= Node.val <= 10^5$

## Code

Merge sort is defined as a sorting algorithm that works by dividing an array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together to form the final sorted array.

class Solution {
// 3->7->5->1
// 3->7  5->1
// 3 7  5 1
ListNode next = middle.next;
middle.next = null;
// 递归调用sortList
// 直到只剩下一个元素的时候开始merge
// 然后返回结果
}

while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}

return slow;
}

private ListNode merge(ListNode a, ListNode b){
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;

while(a != null && b!=null){
if(a.val <= b.val){
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
cur = cur.next;
}

if(a == null) {
cur.next = b;
} else {
cur.next = a;
}

return dummy.next;
}
}