A solution to reduce stack use, Java


  • 0

    Obviously a recursive solution is ok, however it use a lot of stack memory dealing such as "1->10->11->12" and "2->3->4->5->6->13->14->15".

    My solution is to reduce stack use while inserting a "constant list" with the "big list" into the "small list".

    Suppose p.val < q.val, then we should find a "constant list" in q that
    p.val < q.val < ..... < q.somenext.val < p.next < q.somenext.next.val

    We always do the same things, finally we can make it.

    Poor English, don't mind : )

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return null;
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode res;
        if (l1.val < l2.val) {
            res = l1;
            merge(l1, l2);
        } else {
            res = l2;
            merge(l2, l1);
        }
        return res;
    }
    
    public void merge(ListNode small, ListNode big) {
        ListNode p = small;
        ListNode q = big;
        // Node p is smaller than q now
        // Get the proper p.next whose val is bigger than q
        while (p.next != null && p.next.val < q.val) p = p.next;
        if (p.next == null) {
            p.next = q;
            return;
        }
        // temp = q
        // p -> p.next
        // temp -> .... -> q-> q.next
        // p -> temp-> ......-> q -> p.next -> q.next
    
        ListNode temp = q;
        while (q.next != null && q.next.val < p.next.val) q = q.next;
        if (q.next == null) {
            q.next = p.next;
            p.next = temp;
            return;
        } else {
            ListNode pNode = p.next;
            ListNode qNode = q.next;
            q.next = p.next;
            p.next = temp;
            merge(pNode, qNode);
        }
     }

Log in to reply
 

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