Java recursive solution with explanation


  • 0

    Since it is not allowed to modify the lists, and the lowest significant digit is at the end of each lists (The calculation is bottom up), it is suitable to use stack or recursion to solve this problem.
    For instance,
    l1: 7->2->4->3
    l2: 5->6->4
    First calculate the length of each lists and decide which one is longer and the difference of lengths. In this example, l1 is longer with length 4 and l2 has length 3. So for 1 digit (4-3), that is 7, the calculation is longlistNode.val + carry. The value of carry is gained from next digit. But for next digit till the end, both lists nodes should be added together, that is longlistNode.val + shortlistNode.val + carry(get from their next digit). Do the recursion till the end, and do not forget the condition that carry is left 1 after the recursion is done. One more 1 should be added to the head.

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int len1 = 0, len2 = 0, ll = 0, sl = 0;
        ListNode longlist, shortlist, iter1 = l1, iter2 = l2;
        while(iter1!=null){
            iter1 = iter1.next;
            len1++;
        }
        while(iter2!=null){
            iter2 = iter2.next;
            len2++;
        }
        if(len1 > len2){
            longlist = l1;
            shortlist = l2;
            ll = len1;
            sl = len2;
        }
        else{
            longlist = l2;
            shortlist = l1;
            ll = len2;
            sl = len1;
        }
        ListNode dummyAns = new ListNode(0);
        int carry = addTwoHelper(longlist,shortlist,ll-sl,dummyAns);
        if(carry==1){
            ListNode oneMoreDigit = new ListNode(1);
            oneMoreDigit.next = dummyAns.next;
            dummyAns.next = oneMoreDigit;
        }
        return dummyAns.next;
        
    }
    private int addTwoHelper(ListNode longlist, ListNode shortlist, int diff, ListNode ans){
        if(longlist == null||shortlist == null) {
            ans.next = null;
            return 0;
        }
        ListNode curr = new ListNode(0);
        ans.next = curr;
        int carry = 0;
        if(diff>0){
            int currval = longlist.val + addTwoHelper(longlist.next,shortlist,diff-1,curr);
            if(currval>=10){
                curr.val = currval - 10;
                carry = 1;
            }
            else{
                curr.val = currval;
            }
            return carry;
        }
        else{
            int currval = longlist.val+shortlist.val + addTwoHelper(longlist.next,shortlist.next,0,curr);
            if(currval>=10){
                curr.val = currval - 10;
                carry = 1;
            }
            else{
                curr.val = currval;
            }
            return carry;
        }
    }

Log in to reply
 

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