Wrong recursive Java solution, where's my bug?


  • 0
    J

    Instead of loop while, I used recursive solution with wrong output(only [7]). I'm so confused. Where's the bug?

        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode node = new ListNode(0);
            if (l1!=null || l2!=null) {
                int i = (l1==null) ? 0:l1.val;
                int j = (l2==null) ? 0:l2.val;
                if ((i+j)==0) {
                    return null;
                }
                node.val = (i+j)%10;
                ListNode carryNode = new ListNode((i+j)/10);
                ListNode p = (l1==null) ? null:l1.next;
                ListNode q = (l2==null) ? null:l2.next;
                node.next = addTwoNumbers(addTwoNumbers(p,q),carryNode);
            } else {
                return null;
            }
            return node;
        }
    

  • 0
    M
    if ((i+j)==0) {
        return null;
    }
    

    is nulling out zero nodes. Ex:
    3 4 2
    4 6 5
    yields 7 0 8
    The second node is nulled out to return 7


  • 0
    J

    @mhn013 said in Wrong recursive Java solution, where's my bug?:

    if ((i+j)==0) {
        return null;
    }
    

    is nulling out zero nodes. Ex:
    3 4 2
    4 6 5
    yields 7 0 8
    The second node is nulled out to return 7

    Oh yes! You are right. I was foolish to think only about (4+6==10>0) while ignoring the sum with my carryNode("0"). Thanks so much.


  • 0

    Similar solution in C++

    class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
        {
            if(!l1 && !l2) return NULL;
            int sum = 0;
            if(l1) sum += l1->val;
            if(l2) sum += l2->val;
            ListNode *newNode = new ListNode(sum%10), *next = l1? l1->next : NULL;
            sum /= 10;
            if(sum) 
            {
                if(l1 && l1->next) { l1->next->val += sum; next = l1->next; }
                else { next = new ListNode(sum); }
            }
            newNode->next = addTwoNumbers(next, l2? l2->next:NULL);
            return newNode;
        }
    };
    

Log in to reply
 

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