题解 | #单链表的排序#

public ListNode sortInList(ListNode head) {
        //递归出口
        if(head == null || head.next == null) return head;
        //获取到传递进来的head链表的中点
        //使用快慢指针的方式
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //循环借宿 slow慢指针指向的就是中点
        ListNode temp = slow.next;
        slow.next = null;
        //获取到左右两边的节点
        ListNode left = sortInList(head);
        ListNode right = sortInList(temp);
        //创建新的链表
        ListNode h = new ListNode(0);
        ListNode res = h;
        //合并左右两边两个链表
        while(left != null && right != null){
            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 ? left:right;
        return res.next;
}

解题思路：利用二分法的思想，不管这个链表有多长，递归分一半，分到最后得到很多两个一组的链表，对两个一组的链表之间的排序就应该得心应手啦