Java solution using merge sort


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

  • 1
    W

    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
    W

    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.