对一个单链表进行排序。

方法一：构造一个辅助的数组来排序。
Java构造一个集合来存储。先将链表内容存储到集合中去，再对集合进行排序，最后按照顺序取出集合中的数据即可。

    public ListNode sortInLit(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // write code here
        ArrayList<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);//将head的值添加进来
            head = head.next;
        }
        Collections.sort(list); //进行排序
        ListNode p = new ListNode(-1);
        ListNode cur = p;
        for (int i = 0; i < list.size(); i++) {
            cur.next = new ListNode(list.get(i));
            cur = cur.next;
        }
        return p.next;
    }

归并排序

归并排序的思想本质是分治，分和治相结合形成的。
https://blog.csdn.net/justidle/article/details/104203958

归并排序的文章。

找到链表的中点，向左和向右进行归并排序。
最后再合并即可。

  public ListNode sortInList(ListNode head) {
        // write code here
        if (head == null || head.next == null) {
            return head;
        }
        //找到链表的中点
        //奇数节点在中间 偶数节点在左边一个
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            //一个快移动 一个慢移动
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode tmp = slow.next;
        slow.next = null; //两个断开
        ListNode left = sortInList(head); //左边递归
        ListNode right = sortInList(tmp);//右边递归
        //创建一个新的链表
        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;
    }