Difficulty: MediumLinked List

Add Two Numbers

Problem in Plain English

You are given two reversed linked lists whose nodes hold single digits of two non-negative integers. Add the numbers and return the digit sum as a reversed linked list.

Problem Statement

You are given two non-empty linked lists l1 and l2 representing two non-negative integers. The digits are stored in reverse order, so the head holds the least significant digit, and each node contains a single digit.

Add the two numbers and return the sum as a linked list in the same reversed format, creating an extra node when a final carry remains.

Constraints

The number of nodes in each list is in the range [1, 100].
0 <= Node.val <= 9
Each list represents a number with no leading zeros, except the number 0 itself.

Examples

Example 1

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]

The lists encode 342 and 465; their sum 807 encodes as 7 -> 0 -> 8.

Example 2

Input: l1 = [0], l2 = [0]
Output: [0]

Zero plus zero is zero, encoded as a single node.

Example 3

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

The sum 9999999 + 9999 = 10009998 encodes reversed as [8,9,9,9,0,0,0,1].

Intuition

Each node is one decimal column: the head is the ones column, followed by tens and hundreds. In Example 1, add 2 and 5 to write 7, then add 4 and 6 to write 0 and carry 1 into the next column. Adding 3, 4 and that carry writes 8, producing [7,0,8]. The reversed storage already gives the order needed for addition; an exhausted list contributes zero and a remaining carry becomes one extra node.

Approaches

String Conversion

Solution Details

Reveal String Conversion: intuition, complexity, and code

Intuition

Reconstruct each number as a decimal string, add with an arbitrary-precision integer, and rebuild the reversed result. Java BigInteger, Python int and JavaScript BigInt preserve all 100 input digits, unlike Java long or JavaScript Number. This baseline delegates carries to the integer library but pays for strings and decimal conversion.

Step-by-Step Logic

Collect each list into a digit buffer while moving its pointer to next. Example 1 builds "243" from l1 and "564" from l2.
Reverse each buffer and parse with the language's arbitrary-precision integer type. Example 1 reconstructs 342 and 465.
Add the exact integers and convert the sum to decimal text. Example 1 gives "807"; carries are handled inside integer addition.
Create a dummy node and a tail pointer. Scan the sum text from its last character to its first, appending each digit and advancing tail. Example 1 appends 7, then 0, then 8.
Return dummy.next, skipping the placeholder. Example 1 returns [7,0,8].

Why It Works

Reading the nodes yields digits from least to most significant. Reversing that string places every digit at its original decimal position, so parsing it produces exactly the represented integer. Arbitrary-precision addition produces the exact sum without overflow at the stated limits. Reading the sum string from right to left then appends its ones digit, tens digit and remaining digits in the required list order. Even a zero sum has string "0", so the result is never empty.

Dry Run

String Conversion: variable states at each step
action	l1 pointer before → after	l2 pointer before → after	buffers / exact values	tail / output
initialize	2 → 2	5 → 5	a="", b=""	not created
read l1	2 → 4	5 → 5	a="2", b=""	—
read l1	4 → 3	5 → 5	a="24", b=""	—
read l1	3 → null	5 → 5	a="243", b=""	—
read l2	null → null	5 → 6	a="243", b="5"	—
read l2	null → null	6 → 4	a="243", b="56"	—
read l2	null → null	4 → null	a="243", b="564"	—
reverse and parse	null	null	x=342, y=465	—
exact addition	null	null	342 + 465 = 807; sum text="807"	carries handled by integer library
initialize output	null	null	i=2	tail=dummy; []
emit character 2	null	null	"7" → digit 7; i=2 → 1	dummy → first node 7; [7]
emit character 1	null	null	"0" → digit 0; i=1 → 0	first node 7 → second node 0; [7,0]
emit character 0	null	null	"8" → digit 8; i=0 → -1	second node 0 → third node 8; [7,0,8]
stop and return	null	null	all characters consumed	dummy.next → [7,0,8]

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n)

Let n be the longer input length. Traversal, buffer reversal and result-node allocation take O(n) time. Exact addition of O(n)-digit integers is linear, but decimal parsing and formatting are not constant-time: conventional conversion repeatedly multiplies or divides a growing multiword integer, giving a conservative O(n^2) bound. Libraries may use faster conversion algorithms; their APIs do not promise one shared tight bound. Buffers, exact integers, sum text and at most n + 1 returned nodes occupy O(n) space, including the output. The snippets use arbitrary precision for the full 100-node contract.

Code

Solution.java

1// Omit this definition when the platform provides ListNode.2class ListNode {3    int val;4    ListNode next;5    ListNode(int val) { this.val = val; }6}7
8class Solution {9    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {10        StringBuilder a = new StringBuilder();11        StringBuilder b = new StringBuilder();12        while (l1 != null) {13            a.append(l1.val);14            l1 = l1.next;15        }16        while (l2 != null) {17            b.append(l2.val);18            l2 = l2.next;19        }20        java.math.BigInteger x = new java.math.BigInteger(a.reverse().toString());21        java.math.BigInteger y = new java.math.BigInteger(b.reverse().toString());22        String s = x.add(y).toString();23        ListNode dummy = new ListNode(0);24        ListNode tail = dummy;25        for (int i = s.length() - 1; i >= 0; i--) {26            tail.next = new ListNode(s.charAt(i) - '0');27            tail = tail.next;28        }29        return dummy.next;30    }31}

Hints

Hint 1

Reversed storage is a gift: the heads are the ones column, so add from the heads forward like paper arithmetic.

Hint 2

Track one carry number: each column total adds both digits and the incoming carry. Write the remainder on division by 10, and carry the integer quotient forward.

Hint 3

Loop while l1, l2, or carry is nonzero, treating a missing node as 0 so uneven lengths and a final carry just work.

Edge Cases

Uneven lengths, such as a 7-node list plus a 4-node list, where the missing digits count as 0.
A leftover final carry, such as [9] + [9], which needs a brand-new trailing node holding 1.
Both lists holding [0], which returns a single 0 node rather than an empty list.

Common Mistakes and Interview Tips

Dropping the final carry by looping only while nodes remain, which loses the leading 1 in sums like 5 + 5.
Reading .val from a null pointer on uneven lists instead of substituting 0 for the exhausted side.
Converting long lists to machine integers, which overflows once the number exceeds fixed-width range.

Key Takeaway

When digits arrive least-significant first, walk once with a running carry and build the answer behind a dummy head.