Neat Java Merge Sort Solution


  • 2
    J
    public class Solution {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) return head;
            ListNode fakeHead = new ListNode(0);
            fakeHead.next = head;
            ListNode pre = fakeHead;
            ListNode post = fakeHead;
            while (post != null && post.next != null) {
                post = post.next.next;
                pre = pre.next;
            }
            ListNode next = pre.next;
            pre.next = null;
            ListNode a = sortList(next);
            ListNode b = sortList(head);
            return merge(a,b);
        }
        
        public ListNode merge(ListNode a, ListNode b) {
            if (a == null) return b;
            if (b == null) return a;
            if (a.val > b.val) {
                b.next = merge(a,b.next);
                return b;
            }
            else {
                a.next = merge(a.next,b);
                return a;
            }
        }
    }

  • 5
    B

    Given that you are using a recursive call, I don't think it is constant space complexity since you are actually piling n calls on the stack.


  • 0
    Y

    since it is tail recursion, you can do it iteratively


  • 0
    G

    The iterative solution is also not using constant space, I think~


Log in to reply
 

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