Add Two Numbers

Share

Two non-negative integers are stored in linked lists in reverse order (ones digit first). Add the two numbers and return the sum as a linked list in the same format.

Example 1
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807. Digits stored reversed: 2→4→3 means 342.
Example 2
Input: l1 = [0], l2 = [0]
Output: [0]

Solution Approach

Iterate both lists simultaneously, adding digits plus carry. Create a new node for each sum digit.

  • Process digit by digit with carry
  • Create result node for each sum % 10
  • carry = sum / 10; continue until both lists exhausted and carry == 0
Java
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        if (l1 != null) { sum += l1.val; l1 = l1.next; }
        if (l2 != null) { sum += l2.val; l2 = l2.next; }
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
    }
    return dummy.next;
}
Complexity Analysis:

Time complexity: O(max(m,n))
Space complexity: O(max(m,n)). Result list length