解题思路：

归并排序

java">class Solution {public ListNode sortList(ListNode head) {if (head == null || head.next == null) return head;ListNode fast = head.next, slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}ListNode temp = slow.next;slow.next = null;ListNode left = sortList(head);ListNode right = sortList(temp);ListNode dum = new ListNode(0);ListNode cur = dum;while (left != null && right != null) {if (left.val < right.val) {cur.next = left;left = left.next;} else {cur.next = right;right = right.next;}cur = cur.next;}cur.next = left != null ? left : right;return dum.next;}
}