public ListNode sortList(ListNode head) {

        if (head == null || head.next == null)

            return head;

        ListNode prev = null, slow = head, fast = head;

        while (fast != null && fast.next != null) {

            prev = slow;

            slow = slow.next;

            fast = fast.next.next;

        }

        prev.next = null;

        ListNode l1 = sortList(head);

        ListNode l2 = sortList(slow);

        return merge(l1, l2);

    }

    private ListNode merge(ListNode l1, ListNode l2) {

        ListNode dummy = new ListNode(0);

        ListNode p = dummy;

        while (l1 != null && l2 != null) {

            if (l1.val < l2.val) {

                p.next = l1;

                l1 = l1.next;

            }

            else {

                p.next = l2;

                l2 = l2.next;

            }

            p = p.next;

        }

        if (l1 != null) {

            p.next = l1;

        }

        if (l2 != null) {

            p.next = l2;

        }

        return dummy.next;

    }

  public ListNode sortList(ListNode head) {

    if (head == null || head.next == null)

      return head;

    qsort(head, null);

    return head;

  }

    // [begin, end)

    void qsort(ListNode begin, ListNode end) {

        if (begin == end || begin.next == end) return;

        ListNode mid = partition(begin, end);

        qsort(begin, mid);

        qsort(mid.next, end);

    }

    ListNode partition(ListNode begin, ListNode end) {

        int key = begin.val;

        ListNode p = begin;

        ListNode q = begin.next;

        while (q != end) {

            if (q.val < key) {

                p = p.next;

                int tmp = p.val;

                p.val = q.val;

                q.val = tmp;

            }

            q = q.next;

        }

        int tmp = p.val;

        p.val = begin.val;

        begin.val = tmp;

        return p;

    }