Add Two Numbers

MEDIUM✓ CHIP-TIMEDLC #2 — FULL STATEMENT ↗

The drill: Add two non-negative integers that are each stored as a linked list with the least significant digit first, carrying between nodes exactly like grade-school addition — the sum comes back in that same reversed-digit format.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two non-negative integers arrive stored as singly linked lists, with each node holding a single digit and the least significant digit sitting at the head of each list — the reverse of how the number would normally be written.

The job is to add the two numbers together and hand back the sum in that same format: a linked list of digits, least significant first, built from scratch rather than mutating either input.

The lists can be different lengths, and a carry can ripple all the way through — even producing one extra digit beyond the longer of the two input lists.

EX 01

l1 = [5, 6] · l2 = [4]

→ [9, 6]

65 + 4 = 69

EX 02

l1 = [0] · l2 = [0]

→ [0]

ZERO PLUS ZERO

EX 03

l1 = [7, 1, 6] · l2 = [5, 9, 2]

→ [2, 1, 9]

617 + 295 = 912

each list holds up to a few thousand digit nodes
digits are single values zero through nine, no negative numbers
the two input lists may differ in length
a trailing carry can add one extra digit to the result

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Reconstructing each list as one big number, adding, and splitting the sum back into digits works — but only because the language's integers can hold a number of any size. What if they couldn't?

HINT 2 THE STRUCTURE

Grade-school addition never needs the whole number at once — only the current column and whatever carried over from the last one.

HINT 3 ONE STEP FROM THE ANSWER

Walk both lists together, summing corresponding digits plus a running carry; the new digit is that sum mod 10, and sum divided by 10 carries into the next column — keep going past the shorter list until both lists and the carry are exhausted.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE CARRY WALKPATTERN · DIGIT-BY-DIGIT CARRYl1 = [7,1,6] (617) · l2 = [5,9,2] (295)

STEP 1

Add 617+295 stored least-significant-digit-first: l1 reads 7,1,6 and l2 reads 5,9,2. Walk both together one column at a time, carrying between columns.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/add-two-numbers.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        tail = dummy
        carry = 0

        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0
            total = v1 + v2 + carry
            carry, digit = divmod(total, 10)
            tail.next = ListNode(digit)
            tail = tail.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next

TIME O(MAX(N,M))SPACE O(MAX(N,M))PYTHON · RACE PACE · 17 LN

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        def to_int(node):
            num, place = 0, 1
            while node:
                num += node.val * place
                place *= 10
                node = node.next
            return num

        total = to_int(l1) + to_int(l2)

        if total == 0:
            return ListNode(0)

        dummy = ListNode(0)
        tail = dummy
        while total > 0:
            tail.next = ListNode(total % 10)
            tail = tail.next
            total //= 10
        return dummy.next

TIME O(N+M)SPACE O(N+M)PYTHON · TRAINING PACE · 22 LN

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 v1 = l1 != null ? l1.val : 0;
            int v2 = l2 != null ? l2.val : 0;
            int sum = v1 + v2 + carry;
            carry = sum / 10;
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
            l1 = l1 != null ? l1.next : null;
            l2 = l2 != null ? l2.next : null;
        }

        return dummy.next;
    }
}

TIME O(MAX(N,M))SPACE O(MAX(N,M))JAVA · RACE PACE · 20 LN

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        long total = toLong(l1) + toLong(l2);

        if (total == 0) {
            return new ListNode(0);
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (total > 0) {
            tail.next = new ListNode((int) (total % 10));
            tail = tail.next;
            total /= 10;
        }
        return dummy.next;
    }

    private long toLong(ListNode node) {
        long num = 0, place = 1;
        while (node != null) {
            num += node.val * place;
            place *= 10;
            node = node.next;
        }
        return num;
    }
}

TIME O(N+M)SPACE O(N+M)JAVA · TRAINING PACE · 28 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED