DSA-057 · Column addition with carry and fresh output

Add Two Numbers — Reversed Digits

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 22430 deterministic checks. Learner drafts are not executed.

Understand the problem

Add two nonnegative integers represented as singly linked lists of decimal digits in least-significant-first order. Return a canonical reversed-digit chain made entirely of new nodes, leaving inputs unchanged.

Each input is null or a finite acyclic chain of at most 100,000 digits. null means zero. A nonnull chain is canonical: each value is 0..9, and its last (most significant) digit is nonzero unless it is the sole digit 0.
Both methods validate digit range and canonical form before constructing the result. Invalid digits or a multi-node high zero cause IllegalArgumentException with all original fields unchanged. Cycles and concurrent graph changes are outside the contract.
Inputs may share nodes, including the same head, because they are read-only. Output is nonnull even for zero, has no multi-node high zero, and contains only fresh nodes disjoint from every input node. Return the output head, not an int/long approximation.

Examples

Input: A:[2,4,3] (342), B:[5,6,4] (465)
Output: [7,0,8] (807)
Column 0 sums to 7; column 1 sums to 10, emits 0 and carries 1; column 2 sums to 8.
Input: A:[9,9,9], B:[1]
Output: [0,0,0,1]
Carry continues after B ends, then creates a final new most-significant node after both cursors end.
Input: A:null, B:null
Output: fresh [0]
The do/while emits a canonical zero node even with two empty inputs.
Input: A:[1,0], B:[1]
Output: IllegalArgumentException
[1,0] is a noncanonical representation of one under this API; the most-significant zero is rejected.

Before you start

Reversed decimal place values
Dummy-tail output construction and alias ownership

Recognize the structure

Digits already arrive in arithmetic column order, so only a carry connects one position to the next. The numeric value may contain 100,000 digits and cannot be represented by a Java long. New output allocation is required to preserve input ownership, including when inputs alias.

Try before revealing

Hint 1

Reversed digits arrive in exactly the order used by paper-and-pencil column addition.

Hint 2

Use zero for a missing input digit and carry only the quotient by ten.

Hint 3

Append sum%10 into a new node and continue while either cursor or the carry remains.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Convert with arbitrary precision, add, convert back

Validate, collect each reversed digit string, reverse it into normal decimal text, parse with BigInteger, add, then repeatedly divide by ten to emit fresh result digits. For [9,9]+[1], parse 99+1=100 and emit remainders 0,0,1. This is an executable small-case baseline, not an int/long conversion. Arbitrary-precision parsing and repeated division have nonconstant bit costs; the digit-by-digit solution avoids whole-number arithmetic entirely.

Improve the baseline

Validate independently of arithmetic

Traverse both inputs before allocating output so malformed digits and high zeros are rejected consistently. Sharing is harmless because neither traversal writes fields.

Process one column

Let missing input digits be zero. Compute sum=carry+digitA+digitB, append sum%10, and set carry=sum/10. Since input digits are at most nine and carry at most one, sum is at most nineteen.

Emit zero and the final carry

Use a do/while so two zero/null inputs emit one digit. Continue while either input remains or carry!=0. A final carry is one, so the result has canonical most-significant form; nonzero inputs cannot produce an unnecessary high zero.

Why it is correct

Column invariant

After k emitted digits, let Ak and Bk denote the consumed low-k-digit values. Their sum equals the numeric value of the emitted low digits plus carry×10^k. Initially both consumed values and carry are zero.

Preserve the arithmetic

At column k, adding digitA+digitB+carry gives sum. Splitting sum into (sum%10)+10×floor(sum/10) makes the invariant hold for k+1. Bounds 0..19 keep every local int operation safe, independently of total number length.

Finish and preserve ownership

When both cursors and carry are exhausted, the invariant gives the full exact sum. The loop always allocates a new digit Node and never writes input fields, so the output cannot alias inputs even when the inputs share a suffix. Validation precedes construction, and the zero special case is handled by one mandatory iteration.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.math.BigInteger;

public final class Solution {
    public static final class Node {
        public final int value;
        public Node next;
        public Node(int value) { this.value = value; }
    }

    public static Node add(Node a, Node b) {
        validate(a);
        validate(b);
        Node dummy = new Node(0), tail = dummy;
        int carry = 0;
        do {
            int sum = carry + (a == null ? 0 : a.value) + (b == null ? 0 : b.value);
            tail.next = new Node(sum % 10);
            tail = tail.next;
            carry = sum / 10;
            a = a == null ? null : a.next;
            b = b == null ? null : b.next;
        } while (a != null || b != null || carry != 0);
        return dummy.next;
    }

    private static void validate(Node head) {
        Node last = null;
        for (Node p = head; p != null; p = p.next) {
            if (p.value < 0 || p.value > 9) throw new IllegalArgumentException("digit outside 0..9");
            last = p;
        }
        if (head != null && head != last && last.value == 0)
            throw new IllegalArgumentException("noncanonical high zero");
    }

    public static Node baseline(Node a, Node b) {
        validate(a);
        validate(b);
        BigInteger sum = number(a).add(number(b));
        Node dummy = new Node(0), tail = dummy;
        do {
            BigInteger[] parts = sum.divideAndRemainder(BigInteger.TEN);
            tail.next = new Node(parts[1].intValueExact());
            tail = tail.next;
            sum = parts[0];
        } while (sum.signum() != 0);
        return dummy.next;
    }

    private static BigInteger number(Node head) {
        StringBuilder digits = new StringBuilder();
        for (Node p = head; p != null; p = p.next) digits.append(p.value);
        return digits.isEmpty() ? BigInteger.ZERO : new BigInteger(digits.reverse().toString());
    }
}

Read the meaningful blocks

Full validation

The last visited node identifies the most-significant digit. A zero there is rejected only when the list has multiple nodes; null and singleton zero are valid.

Bounded carry arithmetic

No whole-number conversion occurs in add. Each column uses only two digits and one carry, and the dummy is excluded from the output.

Termination condition

Stopping just when a or b becomes null loses unequal-length digits; stopping when both are null loses a pending final carry. The three-part continuation condition is essential.

Complexity

For n,m input lengths and K=max(n,m), validation plus addition takes O(n+m)=O(K+1) time. Auxiliary workspace excluding returned nodes is O(1); output allocation is O(K+1), at most K+1 digit nodes plus a private dummy.

The BigInteger baseline uses O(K+1) digits/bits of stored numeric and textual data up to constant base factors, but parsing and repeated whole-number division are superlinear in the worst case. It is exercised on bounded small inputs, while the optimized 100,000-digit carry test is checked structurally.

Exact-state walkthroughs

Reveal normal and boundary traces

Carry outlives the shorter input

Input: {"a":[9,9,9],"b":[1]} · Reversed result digits: [0,0,0,1]

Step 1 of 6: Validate both canonical inputs before allocating output digits.

Original nodes stay unchanged; newly emitted O nodes will be disjoint from both inputs.

Addition — immutable inputs and fresh output digits

Phase: validated. a: A0 · b: B0

Digits emitted: 0. Carry for the next column: 0. A/B are original read-only nodes; O nodes are freshly allocated output.

A0: 9next → A1a
A1: 9next → A2
A2: 9next → null
B0: 1next → nullb

Cards remain in identity order; follow the named links for traversal order. All output edges must stay disjoint from the input identities.

State after this step
Variable	Value
nodes	`[{"id":"A0","value":9,"next":"A1"},{"id":"A1","value":9,"next":"A2"},{"id":"A2","value":9,"next":null},{"id":"B0","value":1,"next":null}]`
pointers	`{"a":"A0","b":"B0"}`
carry	`0`
column	`0`
phase	`"validated"`

See the affected Java block

 1 import java.math.BigInteger;
 2 
 3 public final class Solution {
 4     public static final class Node {
 5         public final int value;
 6         public Node next;
 7         public Node(int value) { this.value = value; }
 8     }
 9 
10     public static Node add(Node a, Node b) {
11         validate(a);
12         validate(b);
13         Node dummy = new Node(0), tail = dummy;
14         int carry = 0;
15         do {
16             int sum = carry + (a == null ? 0 : a.value) + (b == null ? 0 : b.value);
17             tail.next = new Node(sum % 10);
18             tail = tail.next;
19             carry = sum / 10;
20             a = a == null ? null : a.next;
21             b = b == null ? null : b.next;
22         } while (a != null || b != null || carry != 0);
23         return dummy.next;
24     }
25 
26     private static void validate(Node head) {
27         Node last = null;
28         for (Node p = head; p != null; p = p.next) {
29             if (p.value < 0 || p.value > 9) throw new IllegalArgumentException("digit outside 0..9");
30             last = p;
31         }
32         if (head != null && head != last && last.value == 0)
33             throw new IllegalArgumentException("noncanonical high zero");
34     }
35 
36     public static Node baseline(Node a, Node b) {
37         validate(a);
38         validate(b);
39         BigInteger sum = number(a).add(number(b));
40         Node dummy = new Node(0), tail = dummy;
41         do {
42             BigInteger[] parts = sum.divideAndRemainder(BigInteger.TEN);
43             tail.next = new Node(parts[1].intValueExact());
44             tail = tail.next;
45             sum = parts[0];
46         } while (sum.signum() != 0);
47         return dummy.next;
48     }
49 
50     private static BigInteger number(Node head) {
51         StringBuilder digits = new StringBuilder();
52         for (Node p = head; p != null; p = p.next) digits.append(p.value);
53         return digits.isEmpty() ? BigInteger.ZERO : new BigInteger(digits.reverse().toString());
54     }
55 }
56

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate both canonical inputs before allocating output digits.
Original nodes stay unchanged; newly emitted O nodes will be disjoint from both inputs.
nodes
[{"id":"A0","value":9,"next":"A1"},{"id":"A1","value":9,"next":"A2"},{"id":"A2","value":9,"next":null},{"id":"B0","value":1,"next":null}]
pointers
{"a":"A0","b":"B0"}
carry
0
column
0
phase
"validated"
Emit one new result digit and advance the bounded carry.
sum is at most 19; each O node is new. Continue if either input or a final carry remains.
nodes
[{"id":"A0","value":9,"next":"A1"},{"id":"A1","value":9,"next":"A2"},{"id":"A2","value":9,"next":null},{"id":"B0","value":1,"next":null},{"id":"O0","value":0,"next":null}]
pointers
{"a":"A1","b":null}
carry
1
column
1
phase
"column"
incomingCarry
0
digitA
9
digitB
1
sum
10
emitted
"O0"
Emit one new result digit and advance the bounded carry.
sum is at most 19; each O node is new. Continue if either input or a final carry remains.
nodes
[{"id":"A0","value":9,"next":"A1"},{"id":"A1","value":9,"next":"A2"},{"id":"A2","value":9,"next":null},{"id":"B0","value":1,"next":null},{"id":"O0","value":0,"next":"O1"},{"id":"O1","value":0,"next":null}]
pointers
{"a":"A2","b":null}
carry
1
column
2
phase
"column"
incomingCarry
1
digitA
9
digitB
0
sum
10
emitted
"O1"
Emit one new result digit and advance the bounded carry.
sum is at most 19; each O node is new. Continue if either input or a final carry remains.
nodes
[{"id":"A0","value":9,"next":"A1"},{"id":"A1","value":9,"next":"A2"},{"id":"A2","value":9,"next":null},{"id":"B0","value":1,"next":null},{"id":"O0","value":0,"next":"O1"},{"id":"O1","value":0,"next":"O2"},{"id":"O2","value":0,"next":null}]
pointers
{"a":null,"b":null}
carry
1
column
3
phase
"column"
incomingCarry
1
digitA
9
digitB
0
sum
10
emitted
"O2"
Emit one new result digit and advance the bounded carry.
sum is at most 19; each O node is new. Continue if either input or a final carry remains.
nodes
[{"id":"A0","value":9,"next":"A1"},{"id":"A1","value":9,"next":"A2"},{"id":"A2","value":9,"next":null},{"id":"B0","value":1,"next":null},{"id":"O0","value":0,"next":"O1"},{"id":"O1","value":0,"next":"O2"},{"id":"O2","value":0,"next":"O3"},{"id":"O3","value":1,"next":null}]
pointers
{"a":null,"b":null}
carry
0
column
4
phase
"column"
incomingCarry
1
digitA
0
digitB
0
sum
1
emitted
"O3"
Return the documented outcome after all required mutation or restoration.
The result uses the declared value, identity, and ownership semantics.
result
[0,0,0,1]

Unequal lengths without a final carry

Input: {"a":[2,4],"b":[5]} · Reversed result digits: [7,4]

Step 1 of 4: Validate both canonical inputs before allocating output digits.

Original nodes stay unchanged; newly emitted O nodes will be disjoint from both inputs.

Addition — immutable inputs and fresh output digits

Phase: validated. a: A0 · b: B0

Digits emitted: 0. Carry for the next column: 0. A/B are original read-only nodes; O nodes are freshly allocated output.

A0: 2next → A1a
A1: 4next → null
B0: 5next → nullb

Cards remain in identity order; follow the named links for traversal order. All output edges must stay disjoint from the input identities.

State after this step
Variable	Value
nodes	`[{"id":"A0","value":2,"next":"A1"},{"id":"A1","value":4,"next":null},{"id":"B0","value":5,"next":null}]`
pointers	`{"a":"A0","b":"B0"}`
carry	`0`
column	`0`
phase	`"validated"`

See the affected Java block

 1 import java.math.BigInteger;
 2 
 3 public final class Solution {
 4     public static final class Node {
 5         public final int value;
 6         public Node next;
 7         public Node(int value) { this.value = value; }
 8     }
 9 
10     public static Node add(Node a, Node b) {
11         validate(a);
12         validate(b);
13         Node dummy = new Node(0), tail = dummy;
14         int carry = 0;
15         do {
16             int sum = carry + (a == null ? 0 : a.value) + (b == null ? 0 : b.value);
17             tail.next = new Node(sum % 10);
18             tail = tail.next;
19             carry = sum / 10;
20             a = a == null ? null : a.next;
21             b = b == null ? null : b.next;
22         } while (a != null || b != null || carry != 0);
23         return dummy.next;
24     }
25 
26     private static void validate(Node head) {
27         Node last = null;
28         for (Node p = head; p != null; p = p.next) {
29             if (p.value < 0 || p.value > 9) throw new IllegalArgumentException("digit outside 0..9");
30             last = p;
31         }
32         if (head != null && head != last && last.value == 0)
33             throw new IllegalArgumentException("noncanonical high zero");
34     }
35 
36     public static Node baseline(Node a, Node b) {
37         validate(a);
38         validate(b);
39         BigInteger sum = number(a).add(number(b));
40         Node dummy = new Node(0), tail = dummy;
41         do {
42             BigInteger[] parts = sum.divideAndRemainder(BigInteger.TEN);
43             tail.next = new Node(parts[1].intValueExact());
44             tail = tail.next;
45             sum = parts[0];
46         } while (sum.signum() != 0);
47         return dummy.next;
48     }
49 
50     private static BigInteger number(Node head) {
51         StringBuilder digits = new StringBuilder();
52         for (Node p = head; p != null; p = p.next) digits.append(p.value);
53         return digits.isEmpty() ? BigInteger.ZERO : new BigInteger(digits.reverse().toString());
54     }
55 }
56

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate both canonical inputs before allocating output digits.
Original nodes stay unchanged; newly emitted O nodes will be disjoint from both inputs.
nodes
[{"id":"A0","value":2,"next":"A1"},{"id":"A1","value":4,"next":null},{"id":"B0","value":5,"next":null}]
pointers
{"a":"A0","b":"B0"}
carry
0
column
0
phase
"validated"
Emit one new result digit and advance the bounded carry.
sum is at most 19; each O node is new. Continue if either input or a final carry remains.
nodes
[{"id":"A0","value":2,"next":"A1"},{"id":"A1","value":4,"next":null},{"id":"B0","value":5,"next":null},{"id":"O0","value":7,"next":null}]
pointers
{"a":"A1","b":null}
carry
0
column
1
phase
"column"
incomingCarry
0
digitA
2
digitB
5
sum
7
emitted
"O0"
Emit one new result digit and advance the bounded carry.
sum is at most 19; each O node is new. Continue if either input or a final carry remains.
nodes
[{"id":"A0","value":2,"next":"A1"},{"id":"A1","value":4,"next":null},{"id":"B0","value":5,"next":null},{"id":"O0","value":7,"next":"O1"},{"id":"O1","value":4,"next":null}]
pointers
{"a":null,"b":null}
carry
0
column
2
phase
"column"
incomingCarry
0
digitA
4
digitB
0
sum
4
emitted
"O1"
Return the documented outcome after all required mutation or restoration.
The result uses the declared value, identity, and ownership semantics.
result
[7,4]

Two null zero inputs allocate one result digit

Input: {"a":[],"b":[]} · Reversed result digits: [0]

Step 1 of 3: Validate both canonical inputs before allocating output digits.

Original nodes stay unchanged; newly emitted O nodes will be disjoint from both inputs.

Addition — immutable inputs and fresh output digits

Phase: validated. a: null · b: null

Digits emitted: 0. Carry for the next column: 0. A/B are original read-only nodes; O nodes are freshly allocated output.

No nodes at this step.

Cards remain in identity order; follow the named links for traversal order. All output edges must stay disjoint from the input identities.

State after this step
Variable	Value
nodes	`[]`
pointers	`{"a":null,"b":null}`
carry	`0`
column	`0`
phase	`"validated"`

See the affected Java block

 1 import java.math.BigInteger;
 2 
 3 public final class Solution {
 4     public static final class Node {
 5         public final int value;
 6         public Node next;
 7         public Node(int value) { this.value = value; }
 8     }
 9 
10     public static Node add(Node a, Node b) {
11         validate(a);
12         validate(b);
13         Node dummy = new Node(0), tail = dummy;
14         int carry = 0;
15         do {
16             int sum = carry + (a == null ? 0 : a.value) + (b == null ? 0 : b.value);
17             tail.next = new Node(sum % 10);
18             tail = tail.next;
19             carry = sum / 10;
20             a = a == null ? null : a.next;
21             b = b == null ? null : b.next;
22         } while (a != null || b != null || carry != 0);
23         return dummy.next;
24     }
25 
26     private static void validate(Node head) {
27         Node last = null;
28         for (Node p = head; p != null; p = p.next) {
29             if (p.value < 0 || p.value > 9) throw new IllegalArgumentException("digit outside 0..9");
30             last = p;
31         }
32         if (head != null && head != last && last.value == 0)
33             throw new IllegalArgumentException("noncanonical high zero");
34     }
35 
36     public static Node baseline(Node a, Node b) {
37         validate(a);
38         validate(b);
39         BigInteger sum = number(a).add(number(b));
40         Node dummy = new Node(0), tail = dummy;
41         do {
42             BigInteger[] parts = sum.divideAndRemainder(BigInteger.TEN);
43             tail.next = new Node(parts[1].intValueExact());
44             tail = tail.next;
45             sum = parts[0];
46         } while (sum.signum() != 0);
47         return dummy.next;
48     }
49 
50     private static BigInteger number(Node head) {
51         StringBuilder digits = new StringBuilder();
52         for (Node p = head; p != null; p = p.next) digits.append(p.value);
53         return digits.isEmpty() ? BigInteger.ZERO : new BigInteger(digits.reverse().toString());
54     }
55 }
56

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate both canonical inputs before allocating output digits.
Original nodes stay unchanged; newly emitted O nodes will be disjoint from both inputs.
nodes
[]
pointers
{"a":null,"b":null}
carry
0
column
0
phase
"validated"
Emit one new result digit and advance the bounded carry.
sum is at most 19; each O node is new. Continue if either input or a final carry remains.
nodes
[{"id":"O0","value":0,"next":null}]
pointers
{"a":null,"b":null}
carry
0
column
1
phase
"column"
incomingCarry
0
digitA
0
digitB
0
sum
0
emitted
"O0"
Return the documented outcome after all required mutation or restoration.
The result uses the declared value, identity, and ownership semantics.
result
[0]

Test the contract

Input: null+null
Output: fresh [0]
Canonical zero.
Input: [0]+[0]
Output: fresh [0]
Zero without aliases.
Input: [9,9,9]+[1]
Output: [0,0,0,1]
Carry chain and final digit.
Input: Same [9,9] object passed twice
Output: fresh [8,9,1]; input unchanged
Aliased read-only inputs.
Input: [-1], [10], or [1,0] as an input
Output: IllegalArgumentException
Bad digit/canonical form.

Common mistakes and counterexamples

Convert into long

Counterexample: A 100,000-digit input far exceeds even Long.MAX_VALUE.

Keep only a bounded local column sum and carry; use BigInteger only as a small-test baseline/oracle.

Ignore carry after inputs end

Counterexample: [9]+[1] would incorrectly return [0].

Continue until both cursors are null and carry is zero.

Reuse the longer input tail

Counterexample: When B ends in 999+1, the remaining digits still need carry updates; input sharing also violates fresh-output ownership.

Allocate every output digit and leave both inputs untouched.

Treat null+null as an empty result

Counterexample: The result would not have the promised canonical zero representation.

Run one mandatory iteration and return a new zero node.

Follow-ups

Digits arrive in forward order.

Store input digits on stacks or use carefully justified length-aligned recursion. Reversing caller-owned inputs conflicts with a strictly read-only contract unless temporary mutation is explicitly permitted and restored.

Generalize to base B.

Require 0<=digit<B and a declared base range. The local bound is 2B−1, so widen to long before adding when B may approach the int limit; use division/remainder by B.

Accept noncanonical high zeros.

Decide how inputs are normalized and whether the output trims redundant high zeros. In reversed order those zeros occur at the tail; track the last nonzero output or normalize in a separate pass. Do not silently change the current validation contract.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 126/20,000 characters

Self-review

I separate output allocation from auxiliary space.I prove the processed-columns/carry invariant and local arithmetic bound.I test null zero, aliasing, carry exhaustion, invalid digits, and canonical output.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Linked lists: identity, reachability, and update order

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content and implementations authored for AceYourInterviews. Standard problem names do not imply company-frequency or external platform-difficulty claims.