Arithmetic on Linked Lists

July 2026 · 20 min read

Treat a linked list as a big integer — one decimal digit per node — and a whole family of problems opens up: addition, subtraction, multiplication, and increment. The single most important decision you make before writing any of them is the digit order, because it decides which direction the carry flows and therefore how hard the code is. Get the order right and addition is eight lines; get it wrong and you are fighting the list the whole way.

Why bother modelling a number as a list at all, when a machine int adds in a single instruction? Because a digit list models arbitrary precision. The values in these problems routinely exceed what a 64-bit integer can hold, so you cannot simply walk the list into an int, add, and walk back out — the intermediate conversion overflows and gives a wrong answer. Digit-by-digit arithmetic with an explicit carry is the only correct approach once numbers outgrow the machine word, which is precisely the problem big-integer libraries were built to solve.

A List of Digits Is a Big Integer

The number 342 can live in a list two ways:

• Least-significant digit first (LSD): 2 → 4 → 3. The head is the ones place.
• Most-significant digit first (MSD): 3 → 4 → 2. The head is the hundreds place, exactly how you write it.

Arithmetic carries propagate from least significant to most significant. So LSD order lets the carry flow in the same direction you traverse — head to tail — which is why the classic "Add Two Numbers" stores digits reversed. MSD order reads naturally to a human but forces you to reach the tail before you can start adding, which is the entire difficulty of the "II" variants below.

Add Two Numbers (LeetCode 2) — LSD First

Both numbers are stored least-significant-first, so you add head-to-tail with a running carry and grow the result with a dummy head:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    int carry = 0;
    while (l1 || l2 || carry) {          // one condition, three cases handled
        int sum = carry;
        if (l1) { sum += l1->val; l1 = l1->next; }
        if (l2) { sum += l2->val; l2 = l2->next; }
        carry = sum / 10;
        tail->next = new ListNode(sum % 10);
        tail = tail->next;
    }
    return dummy.next;
}

The elegance is entirely in the loop condition. while (l1 || l2 || carry) unifies what would otherwise be three separate special cases:

• l1 is longer than l2 — keep going on l1 with l2 treated as 0.
• l2 is longer than l1 — the symmetric case.
• a carry survives the last digit — e.g. 5 + 5 = 10 needs a brand-new most-significant node 1, produced by the || carry keeping the loop alive one extra turn.

Without the unified condition you would write a tail loop for the longer number and a trailing if (carry) tail->next = new ListNode(1); after it. One while absorbs all of it. O(max(n, m)) time, O(max(n, m)) nodes for the result.

Dry run: 342 + 465 in reverse-digit form

Result LSD-first: 7 → 0 → 8, which reads as 807 — and indeed 342 + 465 = 807. The carry out of the tens column is what turns a naive 4 + 6 = 10 into a digit 0 plus a carried 1.

Add Two Numbers II (LeetCode 445) — MSD First

Now the digits are stored most-significant-first (3→4→2 for 342), and you are not allowed to know the length in advance cheaply. Addition still needs to start from the least-significant end — the tail. There are three standard ways to get there.

Approach A — reverse both, add, reverse back. Turn it into problem 2, then reverse the result. O(1) extra space, but it mutates the input lists (you can reverse them back to restore). Approach B — two stacks. Push every digit, then pop both stacks together so you consume least-significant digits first, prepending each result node. O(n) space, no mutation. Approach C — recursion with padding. Pad the shorter number with leading zeros, recurse to the tail, and let the carry ripple back up the call stack.

// Approach B: two stacks, no input mutation, result built MSD-first by prepending.
ListNode* addTwoNumbersII(ListNode* l1, ListNode* l2) {
    std::stack<int> s1, s2;
    for (; l1; l1 = l1->next) s1.push(l1->val);
    for (; l2; l2 = l2->next) s2.push(l2->val);

    ListNode* head = nullptr;
    int carry = 0;
    while (!s1.empty() || !s2.empty() || carry) {
        int sum = carry;
        if (!s1.empty()) { sum += s1.top(); s1.pop(); }
        if (!s2.empty()) { sum += s2.top(); s2.pop(); }
        carry = sum / 10;
        ListNode* node = new ListNode(sum % 10);
        node->next = head;      // prepend => most-significant digit ends up first
        head = node;
    }
    return head;
}

Subtraction: Borrow and Sign

Subtraction adds two wrinkles addition does not have: the result can be negative, and you can only subtract a smaller magnitude from a larger one digit by digit. So the algorithm is: compare magnitudes first, subtract the smaller from the larger with a borrow, attach the correct sign, and strip leading zeros from the result (500 - 499 = 1, not 001).

// a, b least-significant-first, with |a| >= |b| guaranteed by the caller.
ListNode* subtractMagnitude(ListNode* a, ListNode* b) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    int borrow = 0;
    while (a) {
        int d = a->val - borrow - (b ? b->val : 0);
        if (d < 0) { d += 10; borrow = 1; } else { borrow = 0; }
        tail->next = new ListNode(d);
        tail = tail->next;
        a = a->next;
        if (b) b = b->next;
    }
    return stripLeadingZeros(dummy.next);
}

// In LSD-first form the most-significant digit is the LAST node,
// so "leading zeros" are trailing zero nodes. Keep at least one digit.
ListNode* stripLeadingZeros(ListNode* head) {
    ListNode* lastNonZero = head;
    for (ListNode* p = head; p; p = p->next)
        if (p->val != 0) lastNonZero = p;
    for (ListNode* p = lastNonZero->next; p; ) { ListNode* nx = p->next; delete p; p = nx; }
    lastNonZero->next = nullptr;
    return head;
}

The sign lives outside the digit list. Compare magnitudes by length first (longer wins), and on a tie compare digit by digit from the most-significant end; if b > a, swap the operands, subtract, and remember to flag the result negative. Each step is O(n), and the whole subtraction is O(n) time, O(n) nodes.

Multiplying Two Lists

Schoolbook multiplication is a double loop: every digit of a times every digit of b lands at position i + j of the product, accumulated, and then the carries are normalised in a single sweep. Multiplication is the one operation that genuinely wants random access by digit position, so it is cleanest to spill the lists into arrays first — a preview of why real bignum libraries never use lists.

// a, b least-significant-first. Returns the product, least-significant-first.
ListNode* multiply(ListNode* A, ListNode* B) {
    std::vector<int> a, b;
    for (; A; A = A->next) a.push_back(A->val);
    for (; B; B = B->next) b.push_back(B->val);

    std::vector<int> prod(a.size() + b.size(), 0);
    for (size_t i = 0; i < a.size(); ++i)
        for (size_t j = 0; j < b.size(); ++j)
            prod[i + j] += a[i] * b[j];         // accumulate partial products

    int carry = 0;                              // normalise carries in one pass
    for (size_t k = 0; k < prod.size(); ++k) {
        int cur = prod[k] + carry;
        prod[k] = cur % 10;
        carry = cur / 10;
    }

    size_t hi = prod.size();                    // strip most-significant zeros
    while (hi > 1 && prod[hi - 1] == 0) --hi;
    ListNode dummy(0);
    ListNode* tail = &dummy;
    for (size_t k = 0; k < hi; ++k) { tail->next = new ListNode(prod[k]); tail = tail->next; }
    return dummy.next;
}

The double loop is O(n·m); the carry-normalisation pass is O(n + m). Accumulating into prod[i + j] before normalising is the crucial move — it separates "collect the raw column sums" from "resolve the carries", so a column can briefly hold a value far larger than 9 without any special handling.

Plus One and the Nines Cascade (LeetCode 369)

Adding one to a number stored most-significant-first is all about the run of trailing nines: 1299 + 1 = 1300. The rightmost non-9 digit absorbs the increment, and every 9 to its right becomes 0. If there is no non-9 digit at all (999), the number grows a new leading digit.

ListNode* plusOne(ListNode* head) {
    ListNode* lastNotNine = nullptr;
    for (ListNode* p = head; p; p = p->next)
        if (p->val != 9) lastNotNine = p;       // rightmost non-9 digit

    if (!lastNotNine) {                          // all nines: 999 + 1 = 1000
        ListNode* one = new ListNode(1);
        one->next = head;
        for (ListNode* p = head; p; p = p->next) p->val = 0;
        return one;
    }
    lastNotNine->val += 1;                       // increment it
    for (ListNode* p = lastNotNine->next; p; p = p->next) p->val = 0;   // zero the tail
    return head;
}

The recursive version is prettier: recurse to the tail, add one there, and return the carry back up. A digit that is 9 turns to 0 and passes the carry along; the first non-9 digit stops it.

int addOne(ListNode* node) {          // returns the carry out of this node
    if (!node) return 1;              // the "+1" itself, arriving past the last digit
    int sum = node->val + addOne(node->next);
    node->val = sum % 10;
    return sum / 10;
}

// Sentinel trick: a leading 0 node absorbs a possible final carry with NO special case.
ListNode* plusOne(ListNode* head) {
    ListNode* sentinel = new ListNode(0);
    sentinel->next = head;
    addOne(sentinel);                 // if all nines, the carry stops in the sentinel
    if (sentinel->val == 0) {         // no overall carry: drop the sentinel
        ListNode* real = sentinel->next;
        delete sentinel;
        return real;
    }
    return sentinel;                  // sentinel became 1: it is the new leading digit
}

Binary to Integer and the Horner Frame (LeetCode 1290)

The gentlest warm-up in this whole family: a list of bits, most-significant-first, to be read as an integer. Fold left with Horner’s scheme:

int getDecimalValue(ListNode* head) {
    int acc = 0;
    for (ListNode* p = head; p; p = p->next)
        acc = acc * 2 + p->val;       // shift the accumulator left, drop in the next bit
    return acc;
}

The pattern acc = acc * base + digit is Horner’s method, and it generalises immediately: use * 10 to parse a decimal list, * 16 for hex, * base for anything. It is a single O(n) pass, O(1) space, and it is exactly how a parser turns a string of digits into a number — no pow, no place-value bookkeeping, just repeated multiply-and-add.

Why Real Bignum Libraries Use Arrays

Every algorithm above is a teaching device. No production big-integer library — GMP, OpenSSL’s BN, Java’s BigInteger — stores one decimal digit per linked node. They use arrays of 32- or 64-bit limbs, and the reasons are the same ones from the memory-model post:

• Words, not digits. A 64-bit limb holds a chunk worth ~19 decimal digits, so a million-digit number needs ~50k limbs, not a million nodes — and each add is one machine instruction, not a per-digit loop.
• Random access. Multiplication, Karatsuba, and FFT-based multiplication all index limbs by position; a list makes that O(n) instead of O(1).
• Locality and SIMD. A contiguous limb array streams through cache and vectorises; a list pointer-chases and stalls.
• No per-digit allocation. One array allocation versus a million new ListNode calls.

The list versions are how you learn carry, borrow, and place value; the array versions are how you ship them.

Check Yourself

Each item gives a situation; pick the statement that is actually true.

Practice

• LeetCode 2 — Add Two Numbers LSD the unified while (l1 || l2 || carry) loop.
• LeetCode 445 — Add Two Numbers II MSD two stacks, no input mutation.
• LeetCode 369 — Plus One Linked List cascade nines to zeros; sentinel for all-nines.
• LeetCode 1290 — Convert Binary Number in a Linked List to Integer Horner acc = acc*2 + bit.
• LeetCode 43 — Multiply Strings schoolbook the array analogue of list multiplication.
• LeetCode 66 — Plus One cascade the same nines cascade on an array.