7.1 Add Two Numbers

7.1.1 Problem Metadata

7.1.2 Description

Given two non-empty linked lc-lists representing non-negative integers in reverse order, add the numbers and return the sum as a linked lc-list.

7.1.3 Examples

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]

7.1.4 Constraints

  • 1 <= len(l1), len(l2) <= 100
  • Digits stored in reverse order; each node contains a single digit

7.1.5 Solution - Iterative Carry Addition

7.1.5.1 Walkthrough

Use two pointers traversing the lc-lists simultaneously. Maintain a carry. At each step sum the corresponding digits and carry, append a node with sum % 10, and update carry to sum / 10. Continue until both lc-lists and the carry are exhausted.

7.1.5.2 Analysis

  • Time Complexity: O(max(m, n))
  • Space Complexity: O(max(m, n)) for the output lc-list

7.1.5.3 Implementation Steps

  1. Initialize dummy head, tail, and carry = 0.
  2. While l1 or l2 is non-null or carry > 0, compute sum = carry + l1.val + l2.val.
  3. Append new node with sum % 10, set carry = sum / 10, advance pointers.
  4. Return dummy.next.

7.1.5.4 Code - Java

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = 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;
        tail.next = new ListNode(sum % 10);
        tail = tail.next;
    }

    return dummy.next;
}