All problems

Add Two Numbers

Medium · linked list

Two non-negative whole numbers are stored in two linked lists, one decimal digit per node. The digits are stored backwards: the head holds the ones digit, the next node the tens digit, then the hundreds, and so on. For example, the list [2, 5, 1] is the number 152.

Add the two numbers and return the sum as a linked list in the same form: ones digit first, one digit per node. The two lists can have different lengths. Apart from the number 0 itself, which is the single node [0], no list ends in a 0 digit, and neither should the list you return.

The nodes you receive are ListNode objects with a val and a next.

Examples

Example 1

Input: l1 = [8, 1, 4], l2 = [5, 6]

Output: [3, 8, 4]

The numbers are 418 and 65, and 418 + 65 = 483, which is stored as 3, 8, 4.

Example 2

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

Output: [0]

Example 3

Input: l1 = [9, 9, 9], l2 = [2]

Output: [1, 0, 0, 1]

999 + 2 = 1001. The carry runs through every digit and adds a new one at the end.

Constraints