public ListNode sortList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode l = null, lc = null, r = null, rc = null, m = head;
        head = head.next;
        while (head != null) {
            if (head.val < m.val) {
                if (lc == null) {
                    lc = l = head;
                } else {
                    lc.next = head;
                    lc = lc.next;
                }
            } else {
                if (rc == null) {
                    rc = r = head;
                } else {
                    rc.next = head;
                    rc = rc.next;
                }
            }
            head = head.next;
        }
        if (lc != null) {
            lc.next = null;
        }
        if (rc != null) {
            rc.next = null;
        }
        l = sortList1(l);
        r = sortList1(r);
        if (l == null) {
            l = m;
        } else {
            lc.next = m;
        }
        m.next = r;
        return l;
    }