Add Two Numbers

The key idea

Walk both lists together one digit at a time, exactly like grade-school addition. At each position add the two digits plus the incoming carry, push sum % 10 as the new digit, and pass sum // 10 forward as the next carry. A leftover carry after both lists end becomes one final node.

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Each node holds one digit in val, and next links to the following digit. Because the digits are reversed, the head of each list is the ones place, so you can add the lists front-to-back while carrying overflow forward, just like adding by hand.

Constraints

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

Examples

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

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

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

Complexity

Time: O(max(m, n)) Space: O(max(m, n))

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →