The Cleanest Java Solution Using Recursion


  • 0
    A

    public class Solution {

    class Result {
        int carry;
        ListNode node;
        public Result(ListNode node, int carry) { 
            this.node = node;
            this.carry = carry;
        }
    } 
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
    
        Result res = helper(l1, l2, len(l1) - len(l2));
        if(res.carry > 0) {
            ListNode node = new ListNode(res.carry);
            node.next = res.node;
            dummy.next = node;
        } else {
            dummy.next = res.node;
        }
        
        return dummy.next;
           
    }
    
    private int len(ListNode head) {
        ListNode cur = head;
        int length = 0;
        while(cur != null) {
            length++;
            cur = cur.next;
        }
        return length;
    }
    
    private Result helper(ListNode l1, ListNode l2, int offset) {
        int sum = 0;
        Result nextResult;
        int carry = 0;
        
        if(offset > 0) {
            nextResult = helper(l1.next, l2, offset - 1);
            sum = l1.val + nextResult.carry;
        } else if(offset < 0) {
            nextResult = helper(l1, l2.next, offset + 1);
            sum = l2.val + nextResult.carry;
        } else {
            if(l1 == null && l2 == null) {
                return new Result(null, 0);
            } 
            nextResult = helper(l1.next, l2.next, 0);
            sum = l1.val + l2.val + nextResult.carry;
        }
        
        ListNode nextNode = nextResult.node;
        carry = sum / 10;
        sum %= 10;
        
        ListNode node = new ListNode(sum);
        node.next = nextNode;
        return new Result(node, carry);
    }
    

    }


Log in to reply
 

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