Add Two Numbers
MediumLinked List
You are given the heads of two non-empty singly linked lists, l1 and l2. Each list represents a non-negative integer, one digit per node, stored in reverse order: the head holds the ones digit, the next node the tens digit, and so on. For example, the list [3, 0, 7] represents the number 703.
Return the head of a new linked list representing l1 + l2, also in reverse digit order.
- The two lists can have different lengths.
- Neither number has leading zeros, except the number 0 itself (the list
[0]). - The numbers can be up to 100 digits long, so converting them to built-in integers is not the intended approach; add digit by digit with a carry.
In the examples, lists are written as arrays from head to tail.
Example 1
- Input:
- l1 = [9, 9], l2 = [1]
- Output:
- [0, 0, 1]
- Explanation
- The lists represent 99 and 1, and
99 + 1 = 100. Written lowest digit first that is[0, 0, 1]: the carry out of the last column becomes an extra node.
Example 2
- Input:
- l1 = [9, 9, 9, 9], l2 = [1]
- Output:
- [0, 0, 0, 0, 1]
- Explanation
9999 + 1 = 10000. Every column produces 0 with a carry of 1, and the final carry adds a fifth node.
Example 3
- Input:
- l1 = [5, 6, 4], l2 = [2]
- Output:
- [7, 6, 4]
- Explanation
- The numbers are 465 and 2, and
465 + 2 = 467, which is[7, 6, 4]in reverse order. Oncel2runs out, the remaining digits ofl1are copied over.
Constraints
- The number of nodes in each list is in the range
[1, 100] 0 <= Node.val <= 9- Neither list has leading zeros except the number
0