Problem Description

Given two non-empty linked lists representing non-negative integres in reverse digit order, combine the numbers and return the result as a linked list.

Basic Iterative Approach

class Solution {
    public ListNode addTwoNumbers(ListNode first, ListNode second) {
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        int carry = 0;
        
        while (first != null && second != null) {
            int total = first.val + second.val + carry;
            carry = total / 10;
            current.next = new ListNode(total % 10);
            first = first.next;
            second = second.next;
            current = current.next;
        }
        
        ListNode remaining = (first != null) ? first : second;
        while (remaining != null) {
            int total = remaining.val + carry;
            carry = total / 10;
            current.next = new ListNode(total % 10);
            remaining = remaining.next;
            current = current.next;
        }
        
        if (carry > 0) {
            current.next = new ListNode(carry);
        }
        
        return dummyHead.next;
    }
}

Simplified Iterative Appproach

class Solution {
    public ListNode addTwoNumbers(ListNode listA, ListNode listB) {
        ListNode dummy = new ListNode(0);
        ListNode pointer = dummy;
        int carryOver = 0;
        
        while (listA != null || listB != null || carryOver != 0) {
            if (listA != null) {
                carryOver += listA.val;
                listA = listA.next;
            }
            if (listB != null) {
                carryOver += listB.val;
                listB = listB.next;
            }
            pointer.next = new ListNode(carryOver % 10);
            pointer = pointer.next;
            carryOver /= 10;
        }
        
        return dummy.next;
    }
}

Reucrsive Implementation

class Solution {
    public ListNode addTwoNumbers(ListNode nodeA, ListNode nodeB) {
        return computeSum(nodeA, nodeB, 0);
    }
    
    private ListNode computeSum(ListNode a, ListNode b, int carry) {
        if (a == null && b == null) {
            return carry == 0 ? null : new ListNode(carry);
        }
        
        if (a == null) {
            a = b;
            b = null;
        }
        
        int total = a.val + carry;
        if (b != null) {
            total += b.val;
        }
        
        a.val = total % 10;
        a.next = computeSum(a.next, (b != null ? b.next : null), total / 10);
        return a;
    }
}