Add Two Numbers

Why it belongs on this sheet

This checks whether you can combine arithmetic state with clean linked-list construction.

Pattern

Digit simulation with carry

Approach

Traverse both lists together, add corresponding digits plus carry, create a new node with the ones place, and carry forward the tens place.

Java solution

class Solution {
  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;
      }

      tail.next = new ListNode(sum % 10);
      tail = tail.next;
      carry = sum / 10;
    }

    return dummy.next;
  }
}

Complexity

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

Interview note

The carry loop condition is worth saying explicitly: it continues while either list has nodes or carry is non-zero.