Java solution using merge sort

  • 7
    public ListNode sortList(ListNode head) {
        if (head == null || == null) return head;
        ListNode slow = head, fast = head, pre = head;
        while(fast != null && != null) {
            pre = slow;
            slow =;
            fast =;
        } = null;
        return merge(sortList(head), sortList(slow));
    public ListNode merge(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val <= l2.val) {
   = merge(, l2);
            return l1;
        } else {
   = merge(l1,;
            return l2;

  • 1

    I think your merge() function has a recursion depth of O(n), which takes O(n) extra space.

  • 0

    Yes, you're right, it's the best solution I can come up with so far. It's pretty straight forward even though the complexity is not better than others.

  • 0

    But that basically violates the requirement of constant space.

    To be constant space, we need to do it iteratively.
    E.g. bottom-up mergesort.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.