题目：

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

题解：

时间复杂度是O(nlogn) 的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是 O(n^2)，其中最适合链表的排序算法是归并排序。

这里用递归的方式进行归并排序。

步骤：

1.找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。

2.对两个子链表分别排序。

3.将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null; //切开成两个链表，前一个链表要和后一个链表断关系
        ListNode h = new ListNode(0);
        ListNode res = h; //最后的结果放虚节点后面
        ListNode left = sortList(head); //head是前一个链表的起点，left为排序完的起点
        ListNode right = sortList(tmp); //tmp是后一个链表的起点，right为排序完的起点
        while (left != null && right != null) { //和21.合并两个有序链表的步骤一样
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next; //结果也要后移一位
        }
        h.next = left == null ? right : left;
        return res.next;
    }
}

参考：力扣