Recursive 8 line C++ solution


  • 12
    G
    class Solution {
    
    	public:
    		ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    			if (l1 == NULL and l2 == NULL) return NULL;
    			else if (l1 == NULL) return l2; 
    			else if (l2 == NULL) return l1; 
    
    			int a = l1->val + l2->val;
    			ListNode *p = new ListNode(a % 10);
    			p->next = addTwoNumbers(l1->next,l2->next);
    			if (a >= 10) p->next = addTwoNumbers(p->next, new ListNode(1));
    			return p;
    		}
      };

  • 0
    S

    Two issues founded:
    #1. If any one of the list become empty in the handling, the rest of the input long list would be linked to the result list. This actually breaks two lists.

    #2. If the input list is very long, will there any stack overflow?


  • 1
    W

    Very cool.

    I think this line is unnecessary:
    if (l1 == NULL and l2 == NULL) return NULL;


  • 0
    S

    Excellent piece of code. Thanks!!


  • 0
    T

    Share my solution using recursion. Comments are welcome.
    The idea is simple: we have 4 subcases giving two nodes as input. 1. both nodes are null. 2. The first one is null. 3. The second node is null. 4. both are not null.

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

Log in to reply
 

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