#20MediumLinked Lists & Math· Digit-by-Digit Addition with Carry

Add Two Numbers

Two non-negative integers are stored as **non-empty** singly linked lists, one decimal digit per node, with the **least significant digit first**. For example, the number 342 is stored as `2 -> 4 -> 3`. Return their sum as a linked list in the same format. Neither number has leading zeros, except the number 0 itself (a single node holding 0). The numbers can have up to 100 digits, so converting them to built-in integers is not a general solution. In the tests each list is written as an array of digits from head to tail.

Input format

l1: array of digits (least significant first), l2: array of digits (least significant first)

Output format

Array of digits of the sum, least significant first

Examples

Input: l1 = [2, 4, 3], l2 = [5, 6, 4]

Output: [7, 0, 8]

342 + 465 = 807, stored as 7 -> 0 -> 8.

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

Output: [8, 9, 9, 9, 0, 0, 0, 1]

9999999 + 9999 = 10009998. The last carry creates an extra node.

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

Output: [0, 1]

5 + 5 = 10: the carry needs a new node even though both lists are finished.

Constraints

1 <= number of nodes in each list <= 100
0 <= Node.val <= 9
Neither list has leading zeros (that is, its last node is non-zero), unless the number is 0.

Study first

Linked Lists & Pointer Nodes

#linked-lists
#math
#simulation