My Java recursive approach


  • 1

    Hello everyone,

    although this problem can be solved by iteration, the recursive approach is interesting too, despite the fact that it has O(n + m) space complexity, where m and n are the lengths of the two lists. Here is my solution, I hope you will find it interesting:

    // recursive function, passing back the next node
        public ListNode addLists(ListNode l1, ListNode l2, int carry){
            // base case
            if(l1 == null && l2 == null && carry == 0)
                return null;
            // add
            int digit = carry;
            digit += (l1 != null) ? l1.val : 0;
            digit += (l2 != null) ? l2.val : 0;
            
            // calculate carry and digit
            carry = digit / 10;
            digit = digit % 10;
            
            // create head
            ListNode head = new ListNode(digit);
            head.next = addLists((l1 != null) ? l1.next : null, (l2 != null) ? l2.next : null, carry);
            
            return head;
                
        }
        
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            // call the recursion
            return addLists(l1,l2,0);
        }
    

Log in to reply
 

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