Java recursive solution with comments


  • 0
    L

    If the length of the two Linked List is m and n respectively, the running complexity of this solution is going to be O(m+n).
    The runtime of this solution on LeetCode is 4ms which beats 31.63% of the java solutions.

    Please feel free to make suggestions in how to improve this.

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            final int carry;
            // We can't recursively use the given method because it doesn't have
            // provisions to deal with carry that may be generated during addition.
            return addTwoNumbers(l1, l2, carry=0);
        }
        
        protected ListNode addTwoNumbers(ListNode l1, ListNode l2, int carry) {
            final ListNode result = new ListNode(carry);
            
            // Even if the listNodes are null, the carry may not be.
            // E.g., (9) + (1) = (0 -> 1)
            if (l1 == null && l2 == null) {
                if (carry != 0) return result;
                else            return null;
            }
            
            if (l1 != null) result.val += l1.val;
            if (l2 != null) result.val += l2.val;
            
            // Generate new carry if necessary and adjust the value.
            int newCarry = 0;
            if (result.val >= 10) {
                result.val = result.val % 10;
                newCarry   = 1;
            }
            result.next = addTwoNumbers(
                l1 != null ? l1.next : null,
                l2 != null ? l2.next : null,
                newCarry
            );
            return result;
        }
    }
    

Log in to reply
 

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