Add Two Numbers II

medium linked list math stack

Problem

Two non-negative integers are represented as linked lists with the most significant digit first. Return their sum as a linked list (same orientation).

Inputl1 = 7→2→4→3, l2 = 5→6→4

Output7→8→0→7

7243 + 564 = 7807.

l1 (digits comma-separated, MSB first)

def add_two_numbers(l1, l2):
    s1, s2 = [], []
    while l1: s1.append(l1.val); l1 = l1.next
    while l2: s2.append(l2.val); l2 = l2.next
    head, carry = None, 0
    while s1 or s2 or carry:
        a = s1.pop() if s1 else 0
        b = s2.pop() if s2 else 0
        total = a + b + carry
        carry = total // 10
        node = ListNode(total % 10)
        node.next = head
        head = node
    return head

function addTwoNumbers(l1, l2) {
  const s1 = [], s2 = [];
  for (let p = l1; p; p = p.next) s1.push(p.val);
  for (let p = l2; p; p = p.next) s2.push(p.val);
  let head = null, carry = 0;
  while (s1.length || s2.length || carry) {
    const a = s1.length ? s1.pop() : 0;
    const b = s2.length ? s2.pop() : 0;
    const total = a + b + carry;
    carry = Math.floor(total / 10);
    head = { val: total % 10, next: head };
  }
  return head;
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> s1 = new ArrayDeque<>(), s2 = new ArrayDeque<>();
        for (ListNode p = l1; p != null; p = p.next) s1.push(p.val);
        for (ListNode p = l2; p != null; p = p.next) s2.push(p.val);
        ListNode head = null; int carry = 0;
        while (!s1.isEmpty() || !s2.isEmpty() || carry > 0) {
            int a = s1.isEmpty() ? 0 : s1.pop();
            int b = s2.isEmpty() ? 0 : s2.pop();
            int total = a + b + carry;
            carry = total / 10;
            ListNode node = new ListNode(total % 10);
            node.next = head; head = node;
        }
        return head;
    }
}

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    stack<int> s1, s2;
    for (auto p = l1; p; p = p->next) s1.push(p->val);
    for (auto p = l2; p; p = p->next) s2.push(p->val);
    ListNode* head = nullptr; int carry = 0;
    while (!s1.empty() || !s2.empty() || carry) {
        int a = 0, b = 0;
        if (!s1.empty()) { a = s1.top(); s1.pop(); }
        if (!s2.empty()) { b = s2.top(); s2.pop(); }
        int total = a + b + carry;
        carry = total / 10;
        auto node = new ListNode(total % 10);
        node->next = head; head = node;
    }
    return head;
}

Explanation

Here the digits are stored with the most significant digit first, but addition naturally starts from the least significant digit. The clever fix is to use two stacks so we can pop the digits in reverse, from rightmost to leftmost.

We push every digit of l1 onto stack s1 and every digit of l2 onto s2. Because a stack is last-in-first-out, popping gives us the lowest-place digits first, exactly the order we need for adding.

We then loop while either stack has digits or a carry remains. Each round we pop a digit from each stack (or use 0 if one is empty), add them with the carry, take total % 10 as the new digit, and update carry = total // 10.

Since the result must also be most-significant-first, we build it by prepending each new node to the front: node.next = head; head = node. This grows the answer in the correct orientation without a final reversal.

Example: 7→2→4→3 (7243) and 5→6→4 (564). Adding from the right gives 3+4=7, 4+6=0 carry 1, 2+5+1=8, then 7, producing 7→8→0→7 = 7807.

Time: O(m + n) Space: O(m + n)